1119.cpp

http://acm.zju.edu.cn 1119

#include <cstdio>
#include <vector>
#include <set>
#define N 1001
using namespace std;

int G[N][N];
int parent[N];
int num[N];
int low[N];
int visited[N];
int counter;
int NumVertex;
int art[N];
int disjset[N];

void FindArt(int v)
{
	visited[v] = 1;
	num[v] = low[v] = counter++;
	for(int i = 1; i <= NumVertex; i++)
	{
		if(G[v][i] == 1)
		{
			if(!visited[i])
			{
				parent[i] = v;
				FindArt(i);
				if(low[i] >= num[v])
					art[v] = 1;
				low[v] = min(low[v], low[i]);
			}
			else if(parent[v] != i)
				low[v] = min(low[v], num[i]);
		}
	}
}
//void FindArt(int v)
//{
//	int w;
//	visited[v] = 1;
//	low[v] = num[v] = counter++;
//	for(int w = 1; w <= NumVertex; w++)
//	{
//		if(G[v][w] == 0)
//			continue;
//		if(!visited[w])
//		{
//			parent[w] = v;
//			FindArt(w);
//			if(low[w] >= num[v])
//				art[v] = 1;
//			low[v] = low[v] < low[w] ? low[v] : low[w];
//		}
//		else if(parent[v] != w)
//			low[v] = low[v] < num[w] ? low[v] : num[w];
//	}
//}

int Find(int v)
{
	if(disjset[v] == 0)
		return v;
	else
		return Find(disjset[v]);
}
int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int s, e;
	int testcase = 1;
	while(scanf("%d", &s))
	{
		if(s == 0)
			break;
		scanf("%d", &e);
		memset(G, 0, sizeof(G));
		memset(parent, 0, sizeof(parent));
		memset(num, 0, sizeof(num));
		memset(low, 0, sizeof(low));
		memset(visited, 0, sizeof(visited));
		memset(art, 0, sizeof(art));
		counter = 1;
		NumVertex = 0;
		if(s > NumVertex)
			NumVertex = s;
		if(e > NumVertex)
			NumVertex = e;
		G[s][e] = G[e][s] = 1;
		while(scanf("%d", &s))
		{
			if(s == 0)
				break;
			scanf("%d", &e);
			if(s > NumVertex)
				NumVertex = s;
			if(e > NumVertex)
				NumVertex = e;
			G[s][e] = G[e][s] = 1;
		}
		FindArt(1);
		int rootchild = 0;
		for(int i = 2; i <= NumVertex; i++)
			if(parent[i] == 1)
				rootchild++;
		if(rootchild > 1)
			art[1] = 1;
		else
			art[1] = 0;
		vector<int> coll;
		for(int i = 1; i <= NumVertex; i++)
			if(art[i] == 1)
				coll.push_back(i);
		if(testcase != 1)
			printf("\n");
		if(coll.size() == 0)
		{
			printf("Network #%d\n", testcase++);
			printf("  No SPF nodes\n");
			continue;
		}
		vector<int> save;
		for(int i = 0; i < coll.size(); i++)
		{
			memset(disjset, 0, sizeof(disjset));
			save.clear();
			for(int j = 1; j <= NumVertex; j++)
				if(G[coll[i]][j] == 1)
				{
					save.push_back(j);
					G[coll[i]][j] = 0;
					G[j][coll[i]] = 0;
				}
			for(int j = 1; j <= NumVertex; j++)
				for(int k = 1; k <= NumVertex; k++)
					if(G[j][k] == 1)
					{
						int jset = Find(j);
						int kset = Find(k);
						if(jset != kset)
							disjset[jset] = kset;
					}
			int NumNet = 0;
			for(int j = 1; j <= NumVertex; j++)
				if(disjset[j] == 0)
					NumNet++;
			NumNet--;
			if(i == 0)
			{
				printf("Network #%d\n", testcase);
			}
			printf("  SPF node %d leaves %d subnets\n", coll[i], NumNet);
			for(int j = 0; j < save.size(); j++)
				G[coll[i]][save[j]] = G[save[j]][coll[i]] = 1;
		}
		testcase++;
	}
}