时间戳 dfs_clock ：说白了就是记录下访问每个结点的次序。假设我们用 pre 保存，那么如果 pre[u] > pre[v]， 那么就可以知道先访问的 v ，，后访问的 u 。
现在给定一条边， (u, v)， 且 u 的祖先为 fa, 如果有 pre[v] < pre[u] && v != fa, 那么 (u, v) 为一条反向边。
1 求连通分量：
相互可达的节点称为一个连通分量；
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <cstring>#include <stack>#include <vector>#include <queue>#include <map>using namespace std;const int maxn = 1000;vector<int> G[maxn];int n;void init(){for(int i=0; i<n; i++) G[i].clear();}int current_cc;///连通分量的编号void dfs(int u){vis[u] = 1;cc[u] = current_cc;for(int i = 0; i < G[u].size(); i++){int v = G[u][i];if(!vis[v]) dfs(v);}}void find_cc(){current_cc = 0;memset(vis,0,sizeof(vis));for(int u = 0; u < n; u++){if(!vis[u]){current_cc ++;dfs(u);}}}int main(){int m, u, v;scanf("%d%d", &n, &m);init();for(int i=0; i<m; i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}find_cc();for(int i = 0; i < n; i++){ ///假设结点是从0开始编号的printf("结点 %d 属于连通分量 %d\n",i,cc[i]);}return 0;}2 无向图的割顶和桥
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <cstring>#include <stack>#include <vector>#include <queue>#include <map>using namespace std;const int maxn = 1000;vector<int> G[maxn];///G用来存图int pre[maxn], dfs_clock, low[maxn], n;///dfs_clock是时间戳,pre[]用来保存时间戳，即结点的访问次序///low[u]表示u及其后代所能连回的最早的祖先的pre[]值///n是结点的个数bool iscut[maxn];///判断第i个节点是不是割点vector< pair<int,int> > bridge;///用来保存桥void init(){for(int i=0; i<=n; i++) G[i].clear();memset(iscut, false, sizeof(iscut));memset(pre, 0, sizeof(pre));dfs_clock = 0;bridge.clear();}///时间戳初始化为0int dfs(int u, int fa){ ///u在DFS树中的父结点是faint lowu = pre[u] = ++dfs_clock;int child = 0; ///子结点数目for(int i=0; i<G[u].size(); i++){int v = G[u][i];if(!pre[v]){ ///没有访问过v, 没有必要用vis标记了child++;int lowv = dfs(v, u);lowu = min(lowu, lowv); ///用后代的 low 函数更新 u 的 low 函数if(lowv >= pre[u]){iscut[u] = true;if(lowv > pre[u]){bridge.push_back(make_pair(u,v));}}///割点的性质}else if(pre[v] < pre[u] && v != fa){ ///(u,v)为反向边lowu = min(lowu, pre[v]); ///用反向边更新 u 的 low 函数}if(fa < 0 && child == 1) iscut[u] = false;}low[u] = lowu;return lowu;}int main(){int m, u, v;scanf("%d%d", &n, &m);init();for(int i=0; i<m; i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}for(int i=0; i<n; i++)if(!pre[i]){dfs(i, -1);}///割点的信息就存在了iscut[]数组中for(int i=0; i<n; i++){ ///将割点输出if(iscut[i]) printf("%d ", i);}putchar('\n');for(int i = 0; i < bridge.size(); i++){///将桥输出printf("%d %d\n",bridge[i].first,bridge[i].second);}return 0;}
样例：
12 120 10 44 88 94 92 32 72 66 73 710 77 11
3 无向图的双连通分量
割顶的bccno无意义：割点的bccno会被多次赋值，所以它的值无意义。
调用结束后， S保证为空：
#include <iostream>#include <cstdlib>#include <cstdio>#include <algorithm>#include <cstring>#include <stack>#include <vector>#include <queue>#include <map>using namespace std;const int maxn = 1000+10;int pre[maxn], iscut[maxn], bccno[maxn], dfs_clock, bcc_cnt;///bccno 是每个节点所属的双连通分量的编号///bcc_cnt是双连通分量的个数vector<int> G[maxn], bcc[maxn];///bcc[]数组记录了每一支双连通分量struct Edge{int u, v;};stack<Edge> S;int dfs(int u, int fa){int lowu = pre[u] = ++dfs_clock;int child = 0;for(int i=0; i<G[u].size(); i++){int v = G[u][i];Edge e = (Edge){u, v};if(!pre[v]){S.push(e);child++;int lowv = dfs(v, u);lowu = min(lowu, lowv);if(lowv >= pre[u]){iscut[u] = true;bcc_cnt++; bcc[bcc_cnt].clear();for(;;){Edge x = S.top(); S.pop();if(bccno[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u);bccno[x.u] = bcc_cnt;}if(bccno[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v);bccno[x.v] = bcc_cnt;}if(x.u == u && x.v == v) break;}}}else if(pre[v] < pre[u] && v != fa){S.push(e);lowu = min(lowu, pre[v]);}}if(fa < 0 && child == 1) iscut[u] = 0;return lowu;}void find_bcc(int n){memset(pre, 0, sizeof(pre));memset(iscut, 0, sizeof(iscut));memset(bccno, 0, sizeof(bccno));dfs_clock = bcc_cnt = 0;for(int i=0; i<n; i++){if(!pre[i]) dfs(i, -1);}}int main(){int m, u, v, n;scanf("%d%d", &n, &m);for(int i=0; i<m; i++){cin>>u>>v;G[u].push_back(v);G[v].push_back(u);}find_bcc(n);printf("%d\n", bcc_cnt); ///双连通分量的个数for(int i=1; i<=bcc_cnt; i++){ ///输出每个双连通分量for(int j=0; j<bcc[i].size(); j++){printf("%d ", bcc[i][j]);}putchar('\n');}return 0;}
样例：
5 60 10 21 22 32 43 4
4 有向图的强连通分量辽远或偏僻的地方，而会常常想起这一次的旅行，
