图的割点和割边

好久都没有写过博客了，想来今天还是写一篇吧

割点

割点：删除某个点后，图不再联通，这样的点叫割点（割顶）
解决方法：
（1）暴力
（2）DFS一遍得到图的一个生成树，若访问到k点，图就会被k点分为两个
部分，一部分访问过另一部分没有被访问过，若k为割点那么，没有被访问过的点至
少会有一个在不经过k的情况下无法回到已访问过的点。那么如何判断存在这样的一
个点v呢：再对v进行一遍深搜若不经过k就不能回到先前访问过的点，则k为割点。
存储方法可以用邻接矩阵或者邻接表，当然用邻接矩阵和暴力基本上没有什么区别，但是可以更好感受一下 （下面就贴上老师的标程）

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int n,m,e[9][9],root;
int num[9]={0},low[9]={0},flag[9]={0},t=0;        //t用来进行时间戳的递增
void dfs(int cur,int father);	//需要传入的两个参数，当前顶点编号和父顶点的编号 

int main(void)
{
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i = 1;i <= n;i++)	//初始化，此处用邻接矩阵(时间复杂度为O(N*N))存储图方便演示割点算法，实际应用中一般都改为邻接表来存储(时间复杂度为O(N+M)) 
    	for(j = 1;j <= n;j++)
    		e[i][j]=0;
    		
    for(i = 1;i <= m;i++)   //输入无向图的每条边 
    {
    	scanf("%d %d",&x,&y);
    	e[x][y] = 1;
    	e[y][x] = 1;
    }
    root=1;
  	dfs(1,root);	//从1号顶点开始进行深度优先遍历
	  
	for(i = 1;i <= n;i++)  //输出割点 
		if(flag[i] == 1)
			printf("\n%d ",i); 
       
    return 0;
}

//割点算法的核心，需要传入的两个参数，当前顶点编号和父顶点的编号		
void dfs(int cur,int father)
{
	int child = 0,i,j;	//child用来记录生成树中当前顶点cur的儿子个数
	
	t++;	//时间戳加1
	num[cur] = t;	//当前顶点cur的时间戳
	low[cur] = t;	//当前顶点cur能够访问到最早顶点的时间戳，刚开始就是自己
	for(i = 1;i <= n;i++)	//枚举与当前顶点cur有边相连的顶点i 
	{
		if(e[cur][i] == 1)
		{
			if(num[i] == 0)	//如果顶点i的时间戳为0，说明顶点i还没有被访问过
			{
				child++;
				//继续往下深度优先遍历 
				dfs(i,cur); //从生成树的角度来说，此时的i为cur的儿子
				//更新当前顶点cur能访问到最早顶点的时间戳
				low[cur] = min(low[cur],low[i]);
				//如果当前顶点不是根结点并且满足low[i]>=num[cur],则当前顶点为割点
				if(cur != root && low[i] >= num[cur])
					flag[cur] = 1;
				//如果当前顶点是根结点，在生成树中根结点必须要有两个儿子，那么这个根节点才是割点
				if(cur == root && child == 2)
					flag[cur] = 1; 
			}
			else if(i != father)  //否则如果顶点i曾经被访问过，并且这个顶点不是当前顶点cur的父亲，
			{                   //则说明此时的i为cur的祖先，因此需要更新当前顶点cur能访问到最早顶点的时间戳 
				low[cur] = min(low[cur],num[i]);			
			} 
		} 
	}
	return;
}

用邻接表也没有什么困难稍微改一下就行

#include <cstdio> 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define maxn 100010
//#define will
using namespace std;

int first[2*maxn],next[2*maxn],cnt;
int n,m,u[2*maxn],v[2*maxn],t;
int root = 1,flag[maxn],num[maxn],low[maxn];
void dfs(int cur,int father)
{
	int child = 0;
	t++;
	num[cur] = t;
	low[cur] = t;
	for(int i = first[cur];i != -1;i = next[i])
	{
		if(num[v[i]] == 0)
		{
			child++;
			dfs(v[i],cur);
			low[cur] = min(low[cur],low[v[i]]);
			if(cur != root && low[v[i]] >= num[cur])
				flag[cur] = 1;
			if(cur == root && child == 2)
				flag[cur] = 1;
		}
		else if(v[i] != father)
			low[cur] = min(low[cur],num[v[i]]);
	}
	return;
}
int main()
{
	#ifdef will
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	#endif
	
	scanf("%d%d",&n,&m);
	memset(first,-1,sizeof(first));
	memset(next,-1,sizeof(next));
	for(int i = 1;i <= m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		//邻接表 
		u[++cnt] = x,v[cnt] = y;
		next[cnt] = first[u[cnt]];
		first[u[cnt]] = cnt;
		u[++cnt] = y,v[cnt] = x;
		next[cnt] = first[u[cnt]];
		first[u[cnt]] = cnt;
	}
	dfs(1,1);
	for(int i = 1;i <= n;i++)
		if(flag[i] == 1)
			printf("%d\n",i);
			
	#ifdef will
	fclose(stdin);
	fclose(stdout);
	#endif
	return 0;
}

这样子好像会有bug？？反正过不掉这道模板题，稍微改一下应该还是行的 （但我不想改了）

割边

割边其实和割点是一个道理只需要把if(cur != root && low[v[i]] >= num[cur])改成if(cur != root && low[v[i]] > num[cur])
下面贴代码 (好像还是有bug还是大bug)

#include <cstdio> 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define maxn 500010
//#define will
using namespace std;

int first[2*maxn],next[2*maxn],cnt;
int n,m,u[2*maxn],v[2*maxn],index,tot;
int root = 1,flag[maxn],num[maxn],low[maxn];
struct node
{
	int x;
	int y;
}ans[2*maxn];
bool cmp(node tx,node ty)
{
	if(tx.x == ty .x)
		return tx.y < ty.y;
	return tx.x < ty.x;
}
void dfs(int cur,int father)
{
//	int child = 0;
	index++;
	num[cur] = index;
	low[cur] = index;
	for(int i = first[cur];i != -1;i = next[i])
	{
		if(num[v[i]] == 0)
		{
//			child++;
			dfs(v[i],cur);
			low[cur] = min(low[cur],low[v[i]]);
			if(cur != root && low[v[i]] >= num[cur])
				ans[++tot].x = cur,ans[tot].y = v[i];
//				printf("%d-%d\n",cur,v[i]);
		}
		else if(v[i] != father)
			low[cur] = min(low[cur],num[v[i]]);
	}
	return;
}
int main()
{
	#ifdef will
	freopen("blocking.in","r",stdin);
	freopen("blocking.out","w",stdout);
	#endif
	
	scanf("%d%d",&n,&m);
	memset(first,-1,sizeof(first));
	memset(next,-1,sizeof(next));
	for(int i = 1;i <= m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		//邻接表 
		u[++cnt] = x,v[cnt] = y;
		next[cnt] = first[u[cnt]];
		first[u[cnt]] = cnt;
		u[++cnt] = y,v[cnt] = x;
		next[cnt] = first[u[cnt]];
		first[u[cnt]] = cnt;
	}
	dfs(1,1);
	sort(ans+1,ans+1+tot,cmp);
	for(int i = 1;i <= tot;i++)
		printf("%d-%d\n",ans[i].x,ans[i].y);
	
	#ifdef will
	fclose(stdin);
	fclose(stdout);
	#endif
	return 0;
}

图的割点和割边

原文：https://www.cnblogs.com/wknclizu/p/11068398.html