poj 1144 割点和桥

割点： 对于一个无向的连通图，如果删除一个点u及其相关的边，会是的新的图不连通，那么点u就称为图G的一个割点。

   记得   首先这个图是  无向的 其次是连通的。

vis[]记录的是节点v当前的访问状态：1表示在栈中，0表示未访问，2表示已经访问过了；

dfn[]记录的是节点v被访问时的深度。

low[] 记录的是节点v 可以到达的点重 深度的最小值。（我之前对这个low的理解不好，现在应该是理解了，请指正）

在深度遍历图的过程中，记录下每个节点的深度。对当前节点cur,以及和它相连的节点i，有来年两种情况：

（1）i没被访问过，这是递归访问i，并且用i可以到达的最早的祖先来更新cur的low值

  (2) i当前在栈中，这是说明图中有一个环，用i的深度更新cur的low值

cur是割点的条件是  cur是根，并且有大于一个的子节点，或者cur不是根，且cur有一个儿子v是的low[v]>=dfn[cur].

(cur,i)是桥的条件：low[i]>dfn[cur].

这道题的输入麻烦了一点。要好好处理，否则会错，

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int v=150;
int edge[v][v];    //图的邻接矩阵
int bridge[v][v],cut[v];     //是否是桥 ，是否是 割点
int low[v],dfn[v],vis[v];

void cut_bridge(int cur,int father,int dep,int n)
{
	vis[cur]=1;dfn[cur]=low[cur]=dep;
	int children=0;
	for(int i=1;i<=n;i++){
		if(edge[cur][i]){
			if(i!=father&&vis[i]==1){
				if(dfn[i]<low[cur] ) low[cur]=dfn[i];
			}
			if(vis[i]==0){
				cut_bridge(i,cur,dep+1,n);
				children++;
				if(low[i]<low[cur]) low[cur]=low[i];
				if((father==-1&&children>1)||(father!=-1&&low[i]>=dfn[cur])) cut[cur]=1;
				if(low[i]>dfn[cur]) bridge[cur][i]=bridge[i][cur]=1;
			}
		}
	}
	vis[cur]=2;
}

int main()
{
	int n;
	while(scanf("%d",&n),n){
		memset(bridge,0,sizeof(bridge));
		memset(edge,0,sizeof(edge));
		memset(cut,0,sizeof(cut));
		memset(vis,0,sizeof(vis));
		memset(dfn,0,sizeof(dfn));
		memset(low,0x3f3f3f3f,sizeof(low));
		int i;
		getchar();
		int temp;
		scanf("%d",&temp);
		while(temp){
			char c=getchar();
			while(c!=‘\n‘){
				int m;
				scanf("%d",&m);
				edge[temp][m]=edge[m][temp]=1;
				c=getchar();
			}
			scanf("%d",&temp);
		}
		int ans=0;
		cut_bridge(1,-1,0,n);    // 对于每个连通块 取一个点x调用这个函数
		for(i=1;i<=n;i++)
			if(cut[i])
				ans++;
		printf("%d\n",ans);
	}
	return 0;
}

poj 1144 割点和桥

原文：http://blog.csdn.net/cnh294141800/article/details/18991929