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 の問題を紹介していきます。
