关节点的求解

SPF

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int edge[1010][1010];//邻接矩阵 
int vis[1010];//表示顶点访问状态 
int node;//顶点数目 
int tmpdfn;//在dfs过程中记录当前的深度优先搜索序数 
int dfn[1010];//每个顶点的dfn值 
int low[1010];//每个顶点的low值，根据该值来判断是否是关节点 
int son;//根节点的子女节点的个数，如果>2，则根节点是关节点 
int subnets[1010];//记录每个节点的联通分量个数（去掉该节点后） 
void dfs(int u)//深度优先搜索，记录每个节点的low值（根据low值判断是否求关节点 
{
	for(int v=1;v<=node;v++)
	{
		//v和u邻接，在生成树中就是2中情况
		//1.v是u的祖先节点，这样(v,u)就是一条边
		//2.v是u的儿子节点 
		if(edge[u][v])
		{
			if(!vis[v])//v还未访问，v是u的儿子节点 
			{
				vis[v]=1;
				tmpdfn++;
				dfn[v]=low[v]=tmpdfn;
				dfs(v);//dfs(v)执行完毕后，low[v]值已求出 
				low[u]=min(low[u],low[v]);//回退的时候，计算顶点u的low值 
				if(low[v]>=dfn[u])
				{
					if(u!=1)subnets[u]++;//去掉该节点后的连通分量个数
					//根节点的子女节点的个数（如果>2，则根节点是关节点 
					if(u==1)son++;
				}
			}
			//此前v已经访问过了，v是u的祖先节点（(v,u)就是一条回边） 
			else
			low[u]=min(low[u],dfn[v]);
		}
	}
}
void init()//初始化函数 
{
	low[1]=dfn[1]=1;
	tmpdfn=1,son=0;
	memset(vis,0,sizeof vis);
	vis[1]=1;
	memset(subnets,0,sizeof subnets);
}
int main()
{
	int i;
	int u,v;//从输入文件中读入发顶点对 
	int find;//是否找到SPF节点的标志 
	int number=1;//测试数据数目 
	while(1)
	{
		scanf("%d",&u);
		if(u==0)break;
		memset(edge,0,sizeof edge);
		node=0;
		scanf("%d",&v);
		if(u>node)node=u;
		if(v>node)node=v;
		edge[u][v]=edge[v][u]=1;
		while(1)
		{
			scanf("%d",&u);
			if(u==0)break;
			scanf("%d",&v);
			if(u>node)node=u;
			if(v>node)node=v;
			edge[u][v]=edge[v][u]=1;
		}
		if(number>1)
		printf("\n");
		printf("Network #%d\n",number);
		number++;
		init();
		dfs(1);
		if(son>1)
		subnets[1]=son-1;
		find=0;
		for(i=1;i<=node;i++)
		{
			if(subnets[i])
			{
				find=1;
				printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1);
			}
		}
		if(!find)printf("  No SPF nodes\n");
 	} 
 	/*
 	1 2
 	5 4
 	3 1
 	3 2
 	3 4
 	3 5
 	0
	 */
	return 0;
}