Poj 1523 SPF(割點 + tarjan算法)

http://poj.org/problem?id=1523

題意：給一個連通網絡，其節點數目<= 1000,求出其割點編号，并求出删除該割點後會被分割成幾個連通塊。

思路：

tarjan算法：從第一個節點開始深度優先搜尋，同時記錄每個節點i的通路次序以及該節點所能到達的最高輩分（深度最低）的祖先，對這兩個數比較确定這個點是否是割點；同時用subnets數組記錄，若是割點并且是搜尋樹的根節點，則它的兒子數就是删除節點 i 後得到的連通分量，若是割點并且是非根節點，當第一次周遊到該節點時還不能确定它是不是割點，之後對于該節點的每一棵子樹若能判斷出該節點是割點，則subnets[i]加1.

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
const int maxn = 1010;

vector <int> edge[maxn];//鄰接表存儲
int subnets[maxn];//記錄節點是否為割點，當是割點時記錄删除它後的連通分量數
int dfn[maxn];//深度優先搜尋時的次序（時間戳）
int low[maxn];//能追溯到的深度最淺的祖先
int vis[maxn];//是否通路過
int cnt;
int son;//根節點兒子數
int maxv;//最大節點數

void Init()
{
	memset(vis,0,sizeof(vis));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(subnets,0,sizeof(subnets));
	cnt = 0;
	son = 0;
}

void tarjan(int u)
{
	vis[u] = 1;
	dfn[u] = low[u] = ++cnt;
	for(int i = 0; i < (int)edge[u].size(); i++)
	{
		int v = edge[u][i];
		if(!vis[v])
		{
			tarjan(v);
			low[u] = min(low[u],low[v]);
			if(low[v] >= dfn[u])//u是割點
			{
				if(u >= 2)
					subnets[u]++;
				else son++;
			}
		}
		else
			low[u] = min(low[u],dfn[v]);
	}
}
void output(int item)
{
	int flag = 0;
	printf("Network #%d\n",item);
	if(son > 1)	subnets[1] = son - 1;
	for(int i = 1; i <= maxv; i++)
	{
		if(subnets[i])
		{
			flag = 1;
			subnets[i] += 1;
			printf("  SPF node %d leaves %d subnets\n",i,subnets[i]);
		}
	}
	if(!flag)
		printf("  No SPF nodes\n");
	printf("\n");
}

int main()
{
	int u,v,f,flag;
	for(int item = 1; ; item++)
	{
		for(int i = 1; i <  maxn; i++)
			edge[i].clear();
		f = 0;
		maxv = -1;
		while(1)
		{
			scanf("%d",&u);
			maxv = max(maxv,u);
			if(u == 0 && f == 0)
			{
				flag = 1;//輸入結束
				break;
			}
			if(u == 0 && f != 0)
			{
				flag = 2;//改組輸入結束
				break;
			}
			scanf("%d",&v);
			maxv = max(maxv,v);
			f = 1;
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		if(flag == 2)
		{
			Init();
			tarjan(1);
			output(item);
		}
		if(flag == 1)
			break;
	}
	return 0;
}