Tarjan算法求强连通分量（桥）
本质上就是DFS
在dfs的时候记录两个数组： dfn, low
dfn[x]: 代表x点dfs到的时间，即时间戳，在同一个dfs树中，dfn越小，就越浅。
low[x]: 代表x点及其后代指出去的边，能返回的最浅的时间戳。
思路
主程序
① 对节点x进行dfs， 同时记录其父节点father
② dfn[x] = low[x] = 当前时间戳
③ 遍历x的所有邻接节点
④ 如果子结点u还没被访问，则继续对其进行dfs，然后更新x的最小可达祖先，即low[x] = min (low[x], low[u])
⑤ 如果子结点u已被访问，且u不是x的父节点father，那么u是x的祖先，记录祖先的dfn值，更新x的最小可达祖先，即low[x] = min(low[x], dfn[u])
求强连通分量
为了存储整个强连通分量，这里挑选的容器是，堆栈。每次一个新节点出现，就进栈，如果这个点有 出度 就继续往下找。直到找到底，每次返回上来都看一看子节点与这个节点的LOW值，谁小就取谁，保证最小的子树根。如果找到DFN［］＝＝LOW［］就说明这个节点是这个强连通分量的根节点（毕竟这个LOW［］值是这个强连通分量里最小的。）最后找到强连通分量的节点后，就将这个栈里，比此节点后进来的节点全部出栈，它们就组成一个全新的强连通分量。
求桥
如果存在一条边<u,v>，有dfn(u) < low(v)，那么这条边就是桥
例题
给定一个连通无向图，求该图的所有桥，即删除该边后图变为不连通。
输入：第一行是测试样例数，接下来是若干连通图例。每个图例的第一行是结点数和边数，然后用结点对表示的边。假定一个图的结点用0, 1, ..., n表示。
输出：对每个连通图，第一行输出桥的数目，然后是所有用结点对表示的边，这些边按照结点对的字典序输出,最后输入隔离符"------"。
输入样例：
2
3 2
0 1
2 0
3 3
0 1
1 2
0 2
输出样例：
2
0,1
0,2
------
0
------
#include <iostream>
#include <vector>
using namespace std;
#define SIZE 1000
struct node{
int index;
int father;
node(int a, int b): index(a), father(b){}
};
typedef vector< vector<node> > Adjacent;
void makegraph(Adjacent& adj){
int n, m;
cin >> n;
cin >> m;
adj.resize(n);
for (int i = 0; i < m; i++){
int u, v;
cin >> u;
cin >> v;
node a(u, -1);
node b(v, -1);
adj[u].push_back(b);
adj[v].push_back(a);
}
}
struct tarjan{
int dfn[SIZE];
int low[SIZE];
int time;
tarjan();
void Tarjan(Adjacent& adj, node& u);
};
tarjan::tarjan(){
for (int i = 0; i < SIZE; i++){
dfn[i] = 0;
low[i] = 0;
}
time = 0;
}
void tarjan::Tarjan(Adjacent& adj, node& u){
time++;
dfn[u.index] = low[u.index] = time;
for (auto &v : adj[u.index]){
if (!dfn[v.index]){
v.father = u.index;
Tarjan(adj, v);
low[u.index] = min(low[u.index], low[v.index]);
}
else{
if (v.index != u.father){
low[u.index] = min(low[u.index], dfn[v.index]);
}
}
}
}
int main(){
int n;
cin >> n;
while(n--){
Adjacent adj;
makegraph(adj);
node u(0, -1);
tarjan t;
t.Tarjan(adj, u);
int count = 0;
vector < pair<int, int> > bridge;
for (int i = 0; i < adj.size(); i++){
for (auto j : adj[i]){
if (t.dfn[i] < t.low[j.index] ){
count++;
bridge.push_back(make_pair(i, j.index));
}
}
}
if (!count){
cout << 0 << endl;
}
else{
cout << count << endl;
for (int i = 0; i < count; i++){
cout << bridge[i].first << ',' << bridge[i].second << endl;
}
}
cout << "------\n";
}
}
