切断点や橋を求めるTarjanのアルゴリズム
グラフ理論において、切断点(cut vertex, articulation point)とは無くす事でグラフの連結成分の数が増える頂点のことをいい、橋(bridge)とは無くす事でグラフの連結成分の数が増える辺のことをいいます。
グラフの頂点集合に対してDFSを行うと森（木の集まり）を構築出来ます。この森を上手く使う事で切断点や森を効率よく見つけることが出来るアルゴリズムがTarjanのアルゴリズムです。
なお、以下ではグラフの頂点数を|V|、辺の数を|E|で表します。
切断点を求めるアルゴリズム
単純に考えると1つ1つの頂点を消してグラフが連結であるかを調べれば良いので、O(|V|*(|V|+|E|))で出来ます。
しかし、Tarjan's Algorithm for articulation pointsを使うとO(|V|+|E|)で切断点を列挙できます。簡単にいうと、それぞれの頂点にDFSで番号をつけていき、各頂点の子（部分木）がその頂点の番号より前の番号につながっていないならば切断点であるということができます。
根だけは特別な処理が必要で、子が2つ以上あれば切断点です。注意すべきなのは、根の子が2つ以上というのは根からの辺が2本以上伸びているという意味ではなく、部分木を2つ以上持っているという意味です。
Kingdom Unityをこのアルゴリズムで解いてみました（本番ではTLEだった）。
橋を求めるアルゴリズム
単純に考えると、切断点と同様に各辺を消してグラフが連結であるかを調べれば良いので、O(|E|*(|V|+|E|))で出来ます。
切断点と似たような理屈で、Tarjan's Algorithm for finding bridgesを使うとO(|V|+|E|)で橋を列挙できます。それぞれの頂点にDFSで番号をつけていき、ある頂点の子（部分木）がその頂点の番号より後の番号にしかつながっていないならばその2点をつなぐ辺は橋であるということができます。
前々から解きたいと思っていたAttack the NEET Princessをこのアルゴリズムで解いてみました。
ただ、この問題は単純に橋を列挙するだけでは駄目で、ゴールまでとのルートとのintersectionを取ります（C++のset_intersectionが便利）。また、入力条件の「There may be more than one roads between two villages.」に注意が必要。
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <algorithm> #include <string> #include <map> //#include <set> #include <queue> //#include <limits> //#include <sstream> //#include <functional> using namespace std; #define len(array) (sizeof (array) / sizeof *(array)) #define rep(i, s, e) for(int i = s;i < e;i++) #define rrep(i, e, s) for(int i = e;s <= i;i--) #define mfill(a, v) fill(a, a + len(a), v) #define mfill2(a, v, t) fill((t *)a, (t *)(a + len(a)), v) #define vsort(v) sort(v.begin(), v.end()) #define rvsort(v, t) sort(v.begin(), v.end(), greater<t>()) #define asort(a) sort(a, a + len(a)) #define rasort(a, t) sort(a, a + len(a), greater<t>()) typedef unsigned int ui; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> P; const int MOD = (int)1e9 + 7; const double EPS = 1e-10; const int INF = 10000000; const int dx[] = {1, -1, 0, 0, 1, -1, -1, 1}; const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1}; const int MAX_N = 10002, MAX_M = 100001, WHITE = 0, GRAY = 1, BLACK = 2; int color[MAX_N], low[MAX_N], pred[MAX_N], d[MAX_N], ttime = 0, reach[MAX_N]; bool used[MAX_M]; vector<int> edge[MAX_N]; vector<int> route, bridge; map<int, int> tab; int hash(int a, int b) { if (a <= b) return a * 10000 + b; else return b * 10000 + a; } void dfs(int v){ color[v] = GRAY; low[v] = d[v] = ++ttime; rep(i, 0, edge[v].size()){ int w = edge[v][i]; if(color[w] == WHITE){ pred[w] = v; dfs(w); if(low[w] > d[v]){ int t = tab[hash(v,w)]; if(t != -1 && used[t] == false){ bridge.push_back(t); used[t] = true; } } low[v] = min(low[v], low[w]); } else if(w != pred[v]) low[v] = min(low[v], d[w]); } color[v] = BLACK; } void bfs(int n){ queue<int> q; int p = n - 1; mfill(pred, -1); q.push(0); while(!q.empty()){ int v = q.front(); q.pop(); if(v == n - 1) break; rep(i, 0, edge[v].size()){ int w = edge[v][i]; if(pred[w] == -1){ pred[w] = v; reach[w] = tab[hash(v, w)]; q.push(w); } } } while(!q.empty()) q.pop(); while(p != 0){ if(tab[hash(p, pred[p])] != -1) route.push_back(reach[p]); p = pred[p]; } } void init(){ ttime = 0; mfill(color, WHITE); mfill(low, INF); mfill(pred, -1); mfill(d, -1); mfill(used, false); mfill(reach, -1); rep(i, 0, len(edge)) edge[i].clear(); bridge.clear(); route.clear(); tab.clear(); } void doIt(){ int n, m, a, b, h; vector<int>::iterator it; while(~scanf("%d%d", &n, &m)){ init(); rep(j, 0, m){ scanf("%d%d", &a, &b); edge[a].push_back(b); edge[b].push_back(a); h = hash(a,b); if (tab.count(h) == 0) tab[h] = j; else tab[h] = -1; } dfs(0); bfs(n); vsort(bridge); vsort(route); bridge.erase(set_intersection(bridge.begin(), bridge.end(), route.begin(), route.end(), bridge.begin()), bridge.end()); printf("%d\n", (int)bridge.size()); if(1 <= bridge.size()){ vsort(bridge); it = bridge.begin(); while(it != bridge.end()) { if(it != bridge.begin()) printf(" %d", *it); else printf("%d", *it); ++it; } } printf("\n"); } } int main() { doIt(); return 0; }
この問題地雷が多くて、TLE, MLE, PEなどいろいろさまざまなエラーを喰らいました^^（MLE、PEとか初めて喰らった）
Attack the NEET Princess Editorial (中国語)
Tarjanのアルゴリズムを理解しやすいページ
Lecture 6: Depth-First Search (pdf)
Algorithm Design and Complexity
