關節點的求解

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;
}