定义

首先要明确各种定义，非常容易搞混：

1. 时间戳：数组一般叫$dfn[\;]$dfn[]，记录点第一次入栈的顺序。
2. 搜索树：
3. 割点：去掉这个点，原无向联通图不再联通。割点集合同理。
4. 割边/桥：去掉这条边，原无向联通图不再联通。
5. 点双联通图：不存在割点的图。判定：顶点数不超过2的无向联通图是点双。顶点数大于2的无向连通图是点双，当且仅当任意两点至少包含在一个简单环内。
6. 边双联通图：不存在割边的图。判定：任意一条边包含在一个环内。
7. 点双联通分量：极大点双联通图，即不存在包含这个点双联通子图的更大的双联通子图。
8. 变双联通分量：同6，点改为边。
9. 边双缩点：去掉割边，一个联通块缩成一个点。
10. 点双缩点：点双缩成一个点，与割点连成图。
11. 强连通分量的树边、前向边、后向边、横插边：1搜索树上的边，2连到子孙，3连到祖先，4连到不在同一棵子树的点。

Tarjan算法

割点和点双

void Tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    if (rt == u && point[u] == -1){ // 孤立的点特判
        dccn++;
        dcc[dccn].clear();
        dcc[dccn].push_back(u);
        return;
    }
    stk[++st] = u;
    for (int i = point[u]; i != -1; i = edge[i].nxt){
        int v = edge[i].v;
        if (!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]);
            // 因为v在u的子树内，所以low[v]可以用于更新low[u]
            if (low[v] >= dfn[u]){ // 子树中没有可以连到父亲上面的边
            	cut[u] = 1;
                dccn++;
                dcc[dccn].clear();
                dcc[dccn].push_back(u); // u是割点，可能包含在多个点双中，不能弹出
                while (1){
                    int w = stk[st];
                    dcc[dccn].push_back(w);
                    st--;
                    if (w == v){ // 做到子树全部弹出为止，不然v的兄弟也会被弹出
                        break;
                    }
                }
            }
        }
        else{
            low[u] = min(low[u], dfn[v]);
            // low表示u的子树中的非树边能到的最小的dfn值，所以不能和low[v]比较，详见下图
        }
    }
}

看这样一张图：

如果$(!dfn[v])$(!dfn[v])时用$low[v]$low[v]更新$low[u]$low[u]，这张图就是一整个点双了。然而并不是，3明显是一个割点。

割边和边双

void Tarjan(int u, int in_e)
{
	dfn[u] = ++idx;
	low[u] = u;
	for (int i = point[u]; i != -1; i = edge[i].nxt){
		if (i == in_e){
			continue;
		}
		int v = edge[i].v;
		if (!dfn[v]){
			Tarjan(v, i^1);
			low[u] = min(low[u], low[v]);
			if (low[v] < dfn[u]){
				cut_e[i] = cut_e[i^1] = 1;
			}
		}
		else{
			low[u] = min(low[u], dfn[v]);
			// 这里写dfn[v]或者low[v]没什么关系，因为v能通过非树边到达的点u肯定也可以
			// low[]甚至可以看成一个类似并查基集的结构
		}
	}
}

求边双只要求出割边之后$dfs$dfs一遍就行了。

强联通分量

强连通分量的算法是找后向边和横插边构成的环。在栈中记录当前节点的祖先，和能到达当前节点祖先的点。如果有边指向栈中节点，那么就可以用栈中节点的$dfn$dfn更新当前节点的$low$low。

void Tarjan(int u)
{
    dfn[u] = low[u] = ++idx;
    stk[++st] = u;
    instk[u] = 1;
    for (int i = point[u]; i != -1; i = edge[i].nxt){
        int v = edge[i].v;
        if (!dfn[v]){
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]){
    // 如果u不能到达他的祖先，那么在回溯之后他就不满足存在栈中的条件了
        cnum++;
        while (1){
            int v = stk[st--];
            col[v] = cnum;
            instk[v] = 0;
            scc[cnum].push_back(v); // scc中记录每一个强联通分量
            if (v == u){
                break;
            }
        }
    }
}

例题

一、poj 2942
Knights of the Round Table
点双＋奇环判定

二、poj 3694
Network
边双，low[]的并查集用法