割点与桥（割边）的定义

在无向图中才有割边和割点的定义

• 割点：无向连通图中，去掉一个顶点及和它相邻的所有边，图中的连通分量数增加，则该顶点称为割点。

• 桥（割边）：无向联通图中，去掉一条边，图中的连通分量数增加，则这条边，称为桥或者割边。

• 割点与桥（割边）的关系：

  （1）有割点不一定有桥,有桥一定存在割点

  （2）桥一定是割点依附的边。

下图中顶点C为割点，但和C相连的边都不是桥。

暴力解决办法解决求解割点集和割边集

• 暴力法的原理就是通过定义求解割点和割边。在图中去掉某个顶点，然后进行DFS遍历，如果连通分量增加，那么该顶点就是割点。如果在图中去掉某条边，然后进行DFS遍历，如果连通分量增加，那么该边就是割边。对每个顶点或者每个边进行一次上述操作，就可以求出这个图的所有割点和割边，我们称之为这个图的割点集和割边集。

• 在具体的代码实现中，并不需要真正删除该顶点和删除依附于该顶点所有边。对于割点，我们只需要在DFS前，将该顶点对应是否已访问的标记置为ture，然后从其它顶点为根进行DFS即可。对于割边，我们只需要禁止从这条边进行DFS后，如果联通分量增加了，那么这条边就是割边。

Tarjan算法的原理

判断一个顶点是不是割点除了从定义，还可以从DFS（深度优先遍历）的角度出发。我们先通过DFS定义两个概念。

假设DFS中我们从顶点U访问到了顶点V（此时顶点V还未被访问过），那么我们称顶点U为顶点V的父顶点，V为U的孩子顶点。在顶点U之前被访问过的顶点，我们就称之为U的祖先顶点。

显然如果顶点U的所有孩子顶点可以不通过父顶点U而访问到U的祖先顶点，那么说明此时去掉顶点U不影响图的连通性，U就不是割点。相反，如果顶点U至少存在一个孩子顶点，必须通过父顶点U才能访问到U的祖先顶点，那么去掉顶点U后，顶点U的祖先顶点和孩子顶点就不连通了，说明U是一个割点。

上图中的箭头表示DFS访问的顺序（而不表示有向图），对于顶点D而言，D的孩子顶点可以通过连通区域1红色的边回到D的祖先顶点C（此时C已被访问过），所以此时D不是割点。

上图中的连通区域2中的顶点，必须通过D才能访问到D的祖先顶点，所以说此时D为割点。再次强调一遍，箭头仅仅表示DFS的访问顺序，而不是表示该图是有向图。

这里我们还需要考虑一个特殊情况，就是DFS的根顶点（一般情况下是编号为0的顶点），因为根顶点没有祖先顶点。其实根顶点是不是割点也很好判断，如果从根顶点出发，一次DFS就能访问到所有的顶点，那么根顶点就不是割点。反之，如果回溯到根顶点后，还有未访问过的顶点，需要在邻接顶点上再次进行DFS，根顶点就是割点。

Tarjan算法的实现细节

在具体实现Tarjan算法上，我们需要在DFS（深度优先遍历）中，额外定义三个数组dfn[]，low[]，parent[]

dfn数组

dnf数组的下标表示顶点的编号，数组中的值表示该顶点在DFS中的遍历顺序(或者说时间戳)，每访问到一个未访问过的顶点，访问顺序的值（时间戳）就增加1。子顶点的dfn值一定比父顶点的dfn值大（但不一定恰好大1，比如父顶点有两个及两个以上分支的情况）。在访问一个顶点后，它的dfn的值就确定下来了，不会再改变。

low数组

• low数组的下标表示顶点的编号，数组中的值表示DFS中该顶点不通过父顶点能访问到的祖先顶点中最小的顺序值（或者说时间戳）。

• 每个顶点初始的low值和dfn值应该一样，在DFS中，我们根据情况不断更新low的值。

• 假设由顶点U访问到顶点V。当从顶点V回溯到顶点U时，如果 \(dfn[v] < low[u]\), 那么 \(low[u] = dfn[v]\).

• 如果顶点U还有它分支，每个分支回溯时都进行上述操作，那么顶点low[u]就表示了不通过顶点U的父节点所能访问到的最早祖先节点。

parent数组

parent[]:下标表示顶点的编号，数组中的值表示该顶点的父顶点编号，它主要用于更新low值的时候排除父顶点，当然也可以其它的办法实现相同的功能。

割点及桥的判定方法

• 割点：判断顶点U是否为割点，用U顶点的dnf值和它的所有的孩子顶点的low值进行比较，如果存在至少一个孩子顶点V满足low[v] >= dnf[u]，就说明顶点V访问顶点U的祖先顶点，必须通过顶点U，而不存在顶点V到顶点U祖先顶点的其它路径，所以顶点U就是一个割点。对于没有孩子顶点的顶点，显然不会是割点。

• 桥（割边）：low[v] > dnf[u] 就说明V-U是桥

需要说明的是，Tarjan算法从图的任意顶点进行DFS都可以得出割点集和割边集。

从上图的结果中我们可以看出，顶点B,顶点E和顶点K为割点，A-B以及E-K和K-L为割边。

点双联通分量

点双联通图的定义为：一个无向图中没有割点的极大联通子图。如图，点双联通分量有 \(\{1,2\},\{2,5\},\{2,3,4\}\)。

可以发现，如果一个子图是点双联通，那么图的顶点全在一个简单环中，如上图 \(\{2,3,4 \}\) 是一个简单环，是一个点双联通子图。特殊地，不超过两个点的子图也一定点双联通。

扩展到点双联通分量，唯一的区别是联通分量是极大的。如果一个节点 \(x\) 能回到它的祖宗 \(y\)，那么它们间的点构成了一个点双联通子图，但是不一定是点双联通分量。比如还有一个 \(y\) 的祖宗 \(z\) 且 \(x\) 也有连向 \(z\) 的边，那么构成了一个更大的点双联通子图。所以，如果一个点是一个点双联通分量中时间戳最小的点，那么当且仅当 子孙有连该点的边，而没有连该点祖先的边。

具体的。开一个栈，如果一个点是第一次访问，那么将它压入栈中。若当前点是割点，那么将栈中从该点到该点入边指向的点间所有的点，即为一个简单环，加入点双联通分量。

void Tarjan(int x, int fa) {
	dfn[x] = low[x] = ++dfn; st.push(x);
	int child = 0 ;
	for (int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to;
		if(!dfn[y]) {
			child++; Tarjan(y, x); low[x] = min(low[y] , low[x]);
			if(low[y] >= dfn[x]) {
				cut[x] = 1; ans[++cnt].push_back(x);
				while(x!=st.top()) ans[cnt].push_back(st.top()), st.pop();				
			}	
		}else if (dfn[x] > dfn[y] && y != fa) low[x] = min(dfn[y], low[x]); 
	}
	if (fa == 0 && child == 1) cut[x] = 0;
	if (fa == 0 && child == 0) G[++cnt].push_back(x);
}

边双联通分量

边双联通分量的定义为：一个无向图中没有割边的极大联通子图。如图，边双联通分量是且仅是全图。

至于求法。先一次 Tarjan 求出所有的割边，把这些割边删掉，即为在求联通分量的时候不访问，然后统计所有的联通分量即为边双联通分量。可以发现，一条边最多存在于一个边双中，而一个点可以存在于多个点双中。所以可以删割边，不能删割点。

void Tarjan(int x, int fa){
    vis[x] = true; low[x] = dfn[x] = ++idx;
    int child = 0;
    for (int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to, z = e[i].z;
    	if (!vis[y]){
            child++; Tarjan(y,x);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x] && !cut[x]) cut[z] = true;
        }else if(y != fa) low[x] = min(low[x], dfn[y]);
	}
}
vector  ans; 
void dfs(int x){//求图中的联通分量 
	for (int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to, z = e[i].z;
		if (vis[y] || cut[z]) continue; //不重复不是割点
		vis[y] = 1; ans.push_back(y);
		dfs(y);
	}
}

强连通分量

强连通分量的定义为：一个有向图中，任意两个点都能互相到达的极大联通子图。如图，强联通分量有 \(\{1,2,3\},\{4\},\{5\}\)。

与点双联通分量相似，如果一个子图是强联通，那么图的顶点全在一个简单环中。简单环是由回祖路构成的。值得一提的是，只有一个点的子图一定是强连通子图。扩展到强连通分量，还满足 子孙有连该点边，而没有连该点祖先的边。

具体的求法与点双联通分量略有不同。因为有向图中谈割点没有意义，所以通过判断一个点不通过它的入边，能不能回到它的祖先。如果能，即为 \(dfn_x = low_x\)，这意味着不存在一条路径，使得 \(x\) 下面的点能回到 \(x\) 的祖先，而能回到自己。所以 \(x\) 及其下面的点构成了一个强联通分量。

void Tarjan(int x) {
	dfn[x] = low[x] = ++idx; st.push(x); vis[x] = 1; 
	int child = 0 ;
	for (int i = head[x]; i; i = e[i].nxt) {
		int y = e[i].to;
		if(!dfn[y]) {
			child++; 
			Tarjan(y); low[x] = min(low[y] , low[x]);		
		}else if(vis[y]) low[x] = min(dfn[y], low[x]); 
	}
	if (dfn[x] == low[x]){
		int y; cnt++;
		do{
			ans[cnt].push_back(y = st.top()); vis[y] = 0; color[y] = cnt;
			st.pop();
		} while (x != y);
	}
}

缩点

在有向图中，将每个强连通分量缩成超级点，超级点通常具有所在强连通分量所有点的有用信息，且如果两个点之间有边，那么它们所在的超级点也有边。缩点后的图是一个 \(\texttt{DAG}\)，有向无环图。

在无向图中，将每个点双联通分量或边双联通分量缩成超级点。超级点通常具有所在强连通分量所有点的有用信息，且如果两个点之间右边，那么它们所在的超级点也有边。缩点后的图是一棵树。

参考文献

• ylxmf2005 的 Tarjan 割点割边 点双边双 强连通缩点

后记

这里也可以结合 Tarjan 求 LCA，离线LCA(Tarjan)算法详解。