AtCoder が提供しているABC(AtCoder Beginner Contest)075 C問題をC++で解いてみました。ABC075は、2017年10月14日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Bridge(Difficulty : 1067)
問題の詳細は、リンク先をご覧ください。
特定の辺を取り除いたときに、グラフが連結しているかを調べます。AtCoder Problems による Difficulty は 1067 でした。
解答案
辺をひとつずつ抜いて、グラフが連結しているか調べます。連結でなければその辺は橋です。グラフが連結しているかは、BFS(幅優先探索:Breadth-First search)、DFS(深さ優先探索:Depth-First Search)、UnionFind を用いて調べることができます。
C++ プログラム例(ABC075C)
BFS(幅優先探索:Breadth-First search)で調べる。
最初に BFS で調べたプログラムを紹介します。
- 特定の辺を抜いてグラフ $G$ を定義します(19ー26行目)。
- キューを用いて頂点 $0$ からの最短距離を求めます(28ー41行目)。
- 最短距離が-1の頂点が存在する場合、グラフは連結していません(43ー48行目)。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i];
--a[i];
--b[i];
}
int result = 0;
for (int i = 0; i < m; ++i) {
vector<vector<int>> G(n);
for (int j = 0; j < m; ++j) {
if (i == j) {
continue;
}
G[a[j]].push_back(b[j]);
G[b[j]].push_back(a[j]);
}
vector<int> dist(n, -1);
queue<int> que;
que.push(0);
dist[0] = 0;
while (!que.empty()) {
int now = que.front();
que.pop();
for (auto next_v : G[now]) {
if (dist[next_v] == -1) {
que.push(next_v);
dist[next_v] = dist[now] + 1;
}
}
}
for (int j = 0; j < n; ++j) {
if (dist[j] == -1) {
++result;
break;
}
}
}
cout << result << endl;
return 0;
}
DFS(深さ優先探索:Depth-First Search)で調べる。
次に DFS で調べたプログラムを紹介します。BFS との差分は以下です。
- ラムダ式を用いて再帰で連結している頂点を求めます(28ー37行目)。
- 訪れていない頂点があれば、グラフは連結していません(39ー44行目)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i];
--a[i];
--b[i];
}
int result = 0;
for (int i = 0; i < m; ++i) {
vector<vector<int>> G(n);
for (int j = 0; j < m; ++j) {
if (i == j) {
continue;
}
G[a[j]].push_back(b[j]);
G[b[j]].push_back(a[j]);
}
vector<bool> seen(n, false);
auto dfs = [&](auto self, int v) -> void {
seen[v] = true;
for (auto next_v : G[v]) {
if (!seen[next_v]) {
self(self, next_v);
}
}
};
dfs(dfs, 0);
for (int j = 0; j < n; ++j) {
if (!seen[j]) {
++result;
break;
}
}
}
cout << result << endl;
return 0;
}
UnionFind で調べる。
最後にUnionFind で調べたプログラムを紹介します。一番簡潔に書けています。UnionFind の実装は、ACL(AtCorder Library)をを使用しました。
- 特定の辺を抜いて UnionFind 木に
merge
していきます(21ー26行目)。 - 特定の辺が同じ UnionFind 木に属していなければ連結していません(28ー30行目)
#include <atcoder/dsu>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
int main()
{
int n, m;
cin >> n >> m;
vector<int> a(m);
vector<int> b(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i];
--a[i];
--b[i];
}
int result = 0;
for (int i = 0; i < m; ++i) {
dsu uf(n);
for (int j = 0; j < m; ++j) {
if (i != j) {
uf.merge(a[j], b[j]);
}
}
if (!uf.same(a[i], b[i])) {
++result;
}
}
cout << result << endl;
return 0;
}
すべて AC(Accepted=正しいプログラム)と判定されました。
最後に
グラフの連結について、3つの異なるアルゴリズムを使って調べました。勉強になりました。
引き続き ABC の問題を紹介していきます。