第三章.md

第三章 图的连通性

3.1 连通图和非连通图

3.2 割点

引入

1. 割点：删去一点u及其所连的边后，原来连通的图形成多个连通块，这个点u即为割点。
2. 搜索树：对图进行深度优先搜索按搜索顺序及节点之间的父子关系产生的树状图。

定义：

1. dfn[cur]：记录节点cur的访问时间，以1开始。
2. low[cur]：记录节点cur能够通过后向边（返祖边，而且不能是父子边）到达的遍历顺序最早（dfn最小）的祖先的dfn值。
3. 父子边e<u,v>：当u是v在搜索树中的父亲时，e<u,v>称为父子边。

判定（tarjan算法）：

割点u须满足以下两点之一：

• u是树根且有多余一个子树；
• 存在v属于u的孩子，low[v]>=dfn[u]。

如何理解判定 2：

当low[v]>=dfn[u]时，在不通过节点 u 的限制下，u 的子节点 v 不能经过其它节点到达 u 的祖先。所以当把 u 删去之后，它的子树独立，即它的子孙节点构成的图是独立的连通分支。

代码：

void tarjan_Gpoint(int cur, int father){
	dfn[cur]=low[cur] = ++idx;          // idx为计数器，深搜访问的次序
	for(int i = head[cur]; i != -1; i = edge[i].pre){
		int to = edge[i].cur;
		if(dfn[to] == 0){
			tarjan_Gpoint(to, cur);
			low[cur] = min(low[to], low[cur]);
			if(low[to] >= dfn[cur]){
				if(cur == father)
					root ++;        // 根的子树个数
				else
					Gpoint[cur] ++;     // 标记cur为割点
			}
		} else {
			low[cur] = min(dfn[to], low[cur]);
		}
	}
}

int solve_Gpoint(){
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	memset(Gpoint, 0, sizeof(Gpoint));
	idx = root = 0;
	tarjan_Gpoint(1, 1);
	int cnt = 0;    // 割点个数
	if(root > 1) // 判定 1
		cnt ++;
	for(int i = 2; i <= n; i ++)
		if(Gpoint[i]) cnt ++;

	return cnt;
}

3.3 割边

引入

1. 割边：删去一条边后，原来连通的图形成多个连通块，这条边e即为割边。

判定（tarjan算法）：

割边 e<u,v> 须满足：

• 存在v属于u的孩子，low[v]>dfn[u]。

如何理解判定：

当low[v]>dfn[u]时，在不通过节点 u 的限制下，u 的子节点 v 不能经过其它节点到达 u，即节点 u，v 之间不存在环路。所以当把 e 删去之后，它的两边构成独立的连通分支。

代码：

priority_queue<Edge> cutEdges; // 所有的割边

void tarjan_cutEdges(int cur, int father){
	dfn[cur]=low[cur] = ++idx;          // idx为计数器，深搜访问的次序
	for(int i = head[cur]; i != -1; i = edge[i].pre){
		int to = edge[i].cur;
		if(cur == father) continue;
		if(dfn[to] == 0){
			tarjan_cutEdges(to, cur);
			low[cur] = min(low[to], low[cur]);
			if(low[to] > dfn[cur]) {
				cutEdges.push(edge[i]); // 标记 edge[i] 为割边
			}
		} else {
			low[cur] = min(dfn[to], low[cur]);
		}
	}
}

void solve_cutEdges(){
	memset(dfn, 0, sizeof(dfn));
	memset(low, 0, sizeof(low));
	idx = 0;
	tarjan_cutEdges(1, 1);
	return;
}

习题

1. 请在 ZJGSU OJ 上编程解决以下题目：
   • 130 炸桥