poj1523 割顶

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int cut[1011], pre[1011];
vector<int> g[1011];
int ans, dfs_clock, son;
int dfs(int u, int fa){
	int lowu = pre[u] = ++dfs_clock;
	int child = 0;
	for (int i = 0; i < g[u].size(); i++){
		int v = g[u][i];
		if (!pre[v]){
			child ++;
			int lowv = dfs(v, u);
			if (pre[u] <= lowv){
				cut[u] ++;
			}
		
			lowu = min(lowu, lowv);
		}
		else if (pre[u] > pre[v]) lowu = min(lowu, pre[v]);
	}
	if (fa < 0)
		cut[u] = child - 1;
	return lowu;
}
int main(){
	int t = 0, u, v, n = -1;
	while (cin>>u && u){
		dfs_clock = ans = 0;
		for (int i = 1; i <=1000; i++) g[i].clear();
		memset(cut, 0, sizeof(cut));
		memset(pre, 0, sizeof(pre));
		while (u){
			cin>>v;
			n = max(n, max(u, v));
			g[u].push_back(v); g[v].push_back(u);
			cin>>u;
		}
		for (int i = 1; i <= n; i++)
		    if (!pre[i]) dfs(i, -1);
		printf("Network #%d\n", ++t);
		bool flag = 0;
		for (int i = 1; i <= n; i++)
		    if (cut[i] > 0) {
			    printf("  SPF node %d leaves %d subnets\n", i, cut[i] + 1);
			    flag = 1;}
        if (!flag) printf("  No SPF nodes\n");
        printf("\n");
	}
}