割点和割边

割点

定义：在一个连通分量中存在一些关键点，如果删除它，会把这个连通分量分成两个或多个，这种点称为割点。

在一个连通分量G中，对任意一点，做DFS，能够访问到所有点，产生一棵“深搜优先生成树”T。

定理1：T的根节点s是割点，当且仅当s有两个或两个以上的孩子节点。

定理2：T中非根节点u是割点，当且仅当u存在一个孩子节点v，v及其后代都没有回退边连回u的祖先。

编程实现定理2：

设u的一个直接后代是v

1) num[u], 记录DFS对每个节点的访问顺序。

2) low[v], 记录v和v的后代能够连回的祖先num。

3) 如果low[v] >= num[u], 说明v及v的后代都没有回退边回到u的祖先，那么u就是一个割点。

4) 搜完后还要对根节点特判是否是割点。

例题：http://poj.org/problem?id=1144

代码实现：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#define ll long long
const int mod = 1e9+7;

using namespace std;

vector<int>edge[1005];
int vis[1005],low[1005],num[1005],gd[1005],n,sum;
void dfs(int s,int f)
{
    int cnt = 0;
    sum++;
    low[s] = num[s] = sum;//赋值，low的初值就是num
	int l = edge[s].size();
	for(int i = 0; i < l; i++){
		int v = edge[s][i];
		if(!num[v]){
			cnt++;//当前节点的孩子个数
			vis[v] = 1;
			dfs(v,s);
			low[s] = min(low[s],low[v]);//用后代更新low值。 
			if(low[v] >= num[s] && s != 1) gd[s] = 1;
		}
		else if(num[v] < num[s] && v != f) low[s] = min(low[s],num[v]);
                //判断回退边，如果回退边的点的序号比s小，那么说明v是s的祖先，更新low[s].
	}
	if(s == 1 && cnt >= 2){
		gd[s] = 1;//特判根节点
	}
}
 
int main()
{
	while(~scanf("%d",&n) && n){
		sum = 0;
		int t,u,v;
		memset(vis,0,sizeof(vis));
		memset(low,0,sizeof(low));
		memset(gd,0,sizeof(gd));
		memset(num,0,sizeof(num));
		while(scanf("%d",&t) && t){
			char c;
			while(1){
	    		scanf("%d%c",&v,&c);
	    		edge[t].push_back(v);
	    		edge[v].push_back(t);
	    		if(c == '\n') break;
	    	}
		}
		dfs(1,-1);
		int ans = 0;
		for(int i = 1; i <= n; i++){
			if(gd[i]) ans++;
		}
		printf("%d\n",ans);
		for(int i = 1; i <= n; i++) edge[i].clear();
	}
	return 0;
}

注意：如果想用vis判断某个点是否已经走过，那么vis要写在for循环外面，不能写在for的if判断里面。

巧妙的判断s和t之间的关键点方法：

从起点s到终点t的路径数等于经过点v的次数，那么点v就是连接s和v的关键点，如果删除这个点，那么s和t不能连通。很好理解，也就是说s到t的所有路径都要经过点v，没有点v这些路径都不能够连接到t点。

例题：https://www.dotcpp.com/oj/problem1433.html

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <set>
#define ll long long
const int mod = 1e9+7;

using namespace std;

vector<int>edge[2005];
int vis[1005],lz = 0,num[1005];
int n,m;
void dfs(int s,int t)
{
	if(s == t){
		lz++;
		for(int i = 1; i <= n; i++){
			if(vis[i]){
				num[i]++;
			}
		}
		return;
	}
	vis[s] = 1;
	int l = edge[s].size();
	for(int i = 0; i < l; i++){
		int v = edge[s][i];
		if(!vis[v]){
			dfs(v,t);
		}
	}
	vis[s] = 0;
}

int main()
{
    int u,v;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; i++){
    	scanf("%d%d",&u,&v);
    	edge[u].push_back(v);
    	edge[v].push_back(u);
	}
	scanf("%d%d",&u,&v);
	dfs(u,v);
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		if(i != u && i != v){
			if(num[i] == lz) cnt++;
		}
	}
	if(cnt) printf("%d\n",cnt);
	else printf("-1\n");
	return 0;
}