应用：线性时间内求出无向图的割点与桥，双连通分量。有向图的强连通分量，必经点和必经边。
主要是求两个东西，dfn和low
时间戳dfn：就是dfs序，也就是每个节点在dfs遍历的过程中第一次被访问的时间顺序。
追溯值low：$low[x]$定义为$min(dfn[subtree(x)中的节点], dfn[通过1条不再搜索树上的边能到达subtree(x)的节点]）$，其中$subtree(x)$是搜索树中以$x$为根的节点。
其实这个值表示的就是这个点所在子树的最先被访问到的节点，作为这个子树的根。
搜索树：在无向连通图中任选一个节点出发进行深度搜索遍历，每个点只访问一次，所有发生递归的边$(x,y)$构成一棵树，称为无向连通图的搜索树。
low计算方法：
先令$low[x] = dfn[x]$， 考虑从$x$出发的每条边$(x,y)$
若在搜索树上$x$是$y$的父节点，令$low[x]=min(low[x], low[y])$
若无向边$(x,y)$不是搜索树上的边，则令$low[x] = min(low[x], dfn[y])$
割边判定法则：
无向边$(x,y)$是桥，当且仅当搜索树上存在$x$的一个子节点$y$，满足：$dfn[x] < low[y]$
这说明从$subtree(y)$出发，在不经过$(x,y)$的前提下，不管走哪条边都无法到达$x$或比$x$更早访问的节点。若把$(x,y)$删除，$subtree(y)$就形成了一个封闭的环境。
桥一定是搜索树中的边，并且一个简单环中的边一定不是桥。
1 void tarjan(int x, int in_edge)
2 {
3 dfn[x] = low[x] = ++num;
4 int flag = 0;
5 for(int i = head[x]; i; i = Next[i]){
6 int y = ver[i];
7 if(!dfn[y]){
8 tarjan(y);
9 low[x] = min(low[x], low[y]);
10 if(low[y] > dfn[x]){
11 bridge[i] = bridge[i ^ 1] = true;
12 }
13 }
14 else if(i != (in_edge ^ 1))
15 low[x] = min(low[x], dfn[y]);
16 }
17 }
18
19 int main()
20 {
21 cin>>n>>m;
22 tot = 1;
23 for(int i = 1; i <= m; i++){
24 int x, y;
25 scanf("%d%d", &x, &y);
26 if(x == y)continue;
27 add(x, y);
28 add(y, x);
29 }
30 for(int i = 1; i <= n; i++){
31 if(!dfn[i]){
32 tarjan(i, 0);
33 }
34 }
35 for(int i = 2; i < tot; i += 2){
36 if(bridge[i])
37 printf("%d %d\n", ver[i ^ 1], ver[i]);
38 }
39 }
割点判定法则：
若$x$不是搜索树的根节点，则$x$是割点当且仅当搜索树上存在$x$的一个子节点$y$，满足：$dfn[x]\leq low[y]$
特别地，若$x$是搜索树地根节点，则$x$是割点当且仅当搜索树上存在至少两个子节点$y_1,y_2$满足上述条件。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<map>
4 #include<set>
5 #include<cstring>
6 #include<algorithm>
7 #include<vector>
8 #include<cmath>
9 #include<stack>
10 #include<queue>
11 #include<iostream>
12
13 #define inf 0x7fffffff
14 using namespace std;
15 typedef long long LL;
16 typedef pair<int, int> pr;
17
18 const int SIZE = 100010;
19 int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
20 int dfn[SIZE], low[SIZE], n, m, tot, num;
21 bool bridge[SIZE * 2];
22
23 void add(int x, int y)
24 {
25 ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
26 }
27
28 void tarjan(int x)
29 {
30 dfn[x] = low[x] = ++num;
31 int flag = 0;
32 for(int i = head[x]; i; i = Next[i]){
33 int y = ver[i];
34 if(!dfn[y]){
35 tarjan(y);
36 low[x] = min(low[x], low[y]);
37 if(low[y] >= dfn[x]){
38 flag++;
39 if(x != root || flag > 1)cut[x] = true;
40 }
41 }
42 else low[x] = min(low[x], dfn[y]);
43 }
44 }
45
46 int main()
47 {
48 cin>>n>>m;
49 tot = 1;
50 for(int i = 1; i <= m; i++){
51 int x, y;
52 scanf("%d%d", &x, &y);
53 if(x == y)continue;
54 add(x, y);
55 add(y, x);
56 }
57 for(int i = 1; i <= n; i++){
58 if(!dfn[i]){
59 root = i;
60 tarjan(i);
61 }
62 }
63 for(int i = 1; i <= n; i++){
64 if(cut[i])printf("%d", i);
65 }
66 puts("are cut-vertexes");
67 }
双连通分量
若一张无向连通图不存在割点，则称它为“点双连通图”。若一张无向连通图不存在桥，则称他为“边双连通图”。
无向图的极大点双连通子图被称为“点双连通分量”，简记为v-DCC。无向连通图的极大边双连通子图被称为“边双连通分量”，简记为e-DCC。
定理1一张无向连通图是点双连通图，当且仅当满足下列两个条件之一：
1.图的顶点数不超过2.
2.图中任意两点都同时包含在至少一个简单环中。
定理2一张无向连通图是边双连通图，当且仅当任意一条边都包含在至少一个简单环中。
边双连通分量求法
求出无向图中所有的桥，删除桥后，每个连通块就是一个边双连通分量。
用Tarjan标记所有的桥边，然后对整个无向图执行一次深度优先遍历（不访问桥边），划分出每个连通块。
1 int c[SIZE], dcc;
2
3 void dfs(int x){
4 c[x] = dcc;
5 for(int i = head[x]; i; i = Next[i]){
6 int y = ver[i];
7 if(c[y] || bridge[i])continue;
8 dfs(y);
9 }
10 }
11
12 //main()
13 for(int i = 1; i <= n; i++){
14 if(!c[i]){
15 ++dcc;
16 dfs(i);
17 }
18 }
19 printf("There are %d e-DCCs.\n", dcc);
20 for(int i = 1; i <= n; i++){
21 printf("%d belongs to DCC %d.\n", i, c[i]);
22 }
e-DCC的缩点
把e-DCC收缩为一个节点，构成一个新的树，存储在另一个邻接表中。
1 int hc[SIZE], vc[SIZE * 2], nc[SIZE * 2], tc;
2 void add_c(int x, int y){
3 vc[++tc] = y;
4 nc[tc] = hc[x];
5 hc[x] = tc;
6 }
7
8 //main()
9 tc = 1;
10 for(int i = 2; i <= tot; i++){
11 int x = ver[i ^ 1];
12 y = ver[i];
13 if(c[x] == c[y])continue;
14 add_c(c[x], c[y]);
15 }
16 printf("缩点之后的森林， 点数%d, 边数%d(可能有重边)\n", dcc, tc / 2);
17 for(int i = 2; i < tc; i++){
18 printf("%d %d\n", vc[i ^ 1], vc[i]);
19 }
点双连通分量的求法
桥不属于任何e-DCC，割点可能属于多个v-DCC
在Tarjan算法过程中维护一个栈，按照如下方法维护栈中的元素：
1.当一个节点第一次被访问时，该节点入栈。
2.当割点判定方法则中的条件$dfn[x]\leq low[y]$成立时，无论$x$是否为根，都要：
（1）从栈顶不断弹出节点，直至节点$y$被弹出
（2）刚才弹出的所有节点与节点$x$一起构成一个v-DCC
1 void tarjan(int x){
2 dfn[x] = low[x] = ++num;
3 stack[++top] = x;
4 iff(x == root && head[x] == 0){
5 dcc[++cnt].push_back(x);
6 return;
7 }
8 int flag = 0;
9 for(int i = head[x]; i; i = Next[i]){
10 int y = ver[i];
11 if(!dfn[y]){
12 tarjan(y);
13 low[x] = min(low[x], low[y]);
14 if(low[y] >= dfn[x]){
15 flag++;
16 if(x != root || flag > 1)cut[x] = true;
17 cnt++;
18 int z;
19 do{
20 z = stack[top--];
21 dcc[cnt].push_back(z);
22
23 }while(z != y);
24 dcc[cnt].push_back(x);
25 }
26 }
27 else low[x] = min(low[x], dfn[y]);
28 }
29 }
30
31 //main()
32 for(int i = 1; i <= cnt; i++){
33 printf("e-DCC #%d:", i);
34 for(int j = 0; j < dcc[i].size(); j++){
35 printf(" %d", dcc[i][j]);
36 }
37 puts("");
38 }
v-DCC的缩点
设图*有$p$个割点和$t$个v-DCC，新图将包含$p+t$个节点。
1 //main
2 num = cnt;
3 for(int i = 1; i <= n; i++){
4 if(cnt[i])new_id[i] = ++num;
5 }
6 tc = 1;
7 for(int i = 1; i <= cnt; i++){
8 for(int j = 0; j < dcc[i].size(); j++){
9 int x = dcc[i][j];
10 if(cut[x]){
11 add_c(i, new_id[x]);
12 add_c(new_id[x], i);
13 }
14 else c[x] = i;
15 }
16 }
17 printf("缩点之后的森林， 点数%d, 边数%d\n", num, tc / 2);
18 printf("编号1~%d的为原图的v-DCC， 编号>%d的为原图割点\n", cnt, cnt);
19 for(int i = 2; i < tc; i += 2){
20 printf("%d %d\n", vc[i ^ 1], vc[i]);
21 }
有向图的强连通分量
一张有向图，若对于图中任意两个节点$x,y$，既存在$x$到$y$的路径，也存在$y$到$x$的路径，则称该有向图是强连通图。
有向图的极大强连通子图被称为强连通分量，简记为SCC。
一个环一定是强连通图，Tarjan算法的基本思路就是对每个点，尽量找到与它能构成环的所有节点。
Tarjan在深度优先遍历的同时维护了一个栈，当访问到节点$x$时，栈中需要保存一下两类节点：
1.搜索树上$x$的祖先节点，记为$anc(x)$
2.已经访问过，并且存在一条路径到达$anc(x)$的节点
实际上栈中的节点就是能与从$x$出发的“后向边”和“横叉边”形成环的节点。
追溯值：
定义为满足一下条件的节点的最小时间戳：
1.该点在栈中。
2.存在一条存subtree(x)出发的有向边，以该点为终点。
计算步骤：
1.当节点$x$第一次被访问时，把$x$入栈，初始化$low[x]=dfn[x]$
2.扫描从$x$出发的每条边$(x,y)$
(1)若$y$没被访问过，则说明$(x,y)$是树枝边，递归访问$y$,从$y$回溯后，令$low[x] = min(low[x], low[y])$
(2)若$y$被访问过且$y$在栈中，令$low[x] = min(low[x], dfn[y])$
3.从$x$回溯之前，判断是否有$low[x] = dfn[x]$。若成立，则不断从栈中弹出节点直至$x$出栈。
强连通分量判定法则
追溯值计算过程中，若从$x$回溯前，有$low[x] = dfn[x]$成立，则栈中从$x$到栈顶的所有节点构成一个强连通分量。
如果$low[x]=dfn[x]$，说明$subtree(x)$中的节点不能与栈中其他节点一起构成环。另外，因为横叉边的终点时间戳必定小于起点时间戳，所以$subtree(x)$中的节点也不可能直接到达尚未访问的节点（时间戳更大）
1 const int N = 100010, M = 1000010;
2 int ver[M], Next[M], head[N], dfn[N], low[N];
3 int stack[N], ins[N], c[N];
4 vector<int>scc[N];
5 int n, m, tot, num, top, cnt;
6
7 void add(int x, int y){
8 ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
9 }
10
11 void tarjan(int x){
12 dfn[x] = low[x] = ++num;
13 stack[++top] = x, ins[x] - 1;
14 for(int i = head[x]; i; i = Next[i]){
15 if(!dfn[ver[i]]){
16 tarjan(ver[i]);
17 low[x] = min(low[x], low[ver[i]]);
18 }else if(ins[ver[i]]){
19 low[x] = min(low[x], dfn[ver[i]]);
20 }
21 }
22 if(dfn[x] == low[x]){
23 cnt++;
24 int y;
25 do{
26 y = stack[top--], ins[y] = 0;
27 c[y] = cnt, scc[cnt].push_back(y);
28 }while(x != y);
29 }
30 }
31
32 int main(){
33 cin>>n>>m;
34 for(int i = 1; i <= m; i++){
35 int x, y;
36 scanf("%d%d", &x, &y);
37 add(x, y);
38 }
39 for(int i = 1; i <= n; i++){
40 if(!dfn[i])tarjan(i);
41 }
42 }
缩点
1 void add_c(int x, int y){
2 vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc;
3 }
4
5 //main
6 for(int x = 1; x <= n; x++){
7 for(int i = head[x]; i; i = Next[i]){
8 int y = ver[i];
9 if(c[x] == c[y])continue;
10 add_c(c[x], c[y]);
11 }
12 }
李煜东的《图连通性若干扩展问题探讨》，有点难。