题目要求割顶集，并且还要求出去掉割顶之后剩下的图连通数目。
tarjan算法求出割顶后直接枚举就可以了吧。
一开始想到利用iscut[u]的次数也就是点u被判定为割顶的次数求连通分量数，还有利用与结点u相连的点的bccno不同的编号来判定，都是不行的，具体原因自己想清楚比较好。
以后就不会犯这样的错误了。
代码：
#include <iostream> #include <sstream> #include <cstdio> #include <climits> #include <cstring> #include <cstdlib> #include <string> #include <stack> #include <map> #include <cmath> #include <vector> #include <queue> #include <algorithm> #define esp 1e-6 #define pi acos(-1.0) #define pb push_back #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mp(a, b) make_pair((a), (b)) #define in freopen("in.txt", "r", stdin); #define out freopen("out.txt", "w", stdout); #define print(a) printf("%d ",(a)); #define bug puts("********))))))"); #define stop system("pause"); #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) #define inf 0x0f0f0f0f using namespace std; typedef long long LL; typedef vector<int> VI; typedef pair<int, int> pii; typedef vector<pii,int> VII; typedef vector<int>:: iterator IT; const int maxn = 2000; int pre[maxn], iscut[maxn], vis[maxn], low[maxn], bccno[maxn], dfs_clock, bcc_cnt; VI g[maxn], bcc[maxn]; int flag; struct edge { int u, v; edge(int u, int v):u(u), v(v) {} }; stack<edge> S; 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]; edge e = edge(u, v); if(!pre[v]) { S.push(e); child++; int lowv = dfs(v, u); lowu = min(lowu, lowv); if(lowv >= pre[u]) { bcc_cnt++; bcc[bcc_cnt].clear(); iscut[u] = 1; for(;;) { edge x = S.top(); S.pop(); if(bccno[x.u] != bcc_cnt) { bccno[x.u] = bcc_cnt; bcc[bcc_cnt].pb(x.u); } if(bccno[x.v] != bcc_cnt) { bccno[x.v] = bcc_cnt; bcc[bcc_cnt].pb(x.v); } if(x.u == u && x.v == v) break; } } } else if(pre[v] < pre[u] && v != fa) { S.push(e); lowu = min(lowu, pre[v]); } } if(child == 1 && fa < 0) { iscut[u] = 0; } return low[u] = lowu; } void find_bcc(int n) { memset(pre, 0, sizeof(pre)); memset(iscut, 0, sizeof(iscut)); memset(bccno, 0, sizeof(bccno)); dfs_clock = bcc_cnt = 0; for(int i = 1; i <= n; i++) if(!pre[i]) dfs(i, -1); } void dfs1(int u) { vis[u] = 1; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(!vis[v]) { dfs1(v); } } } void init(void) { for(int i = 0; i < maxn; i++) g[i].clear(); } int main(void) { int n; int u, v; int t = 0; while(scanf("%d", &u), u) { init(); flag = 0; n = 0; scanf("%d", &v); g[u].pb(v); g[v].pb(u); n = max(max(u, v), n); while(scanf("%d", &u), u) { scanf("%d", &v); g[u].pb(v); g[v].pb(u); n = max(max(u, v), n); } find_bcc(n); if(t) puts(""); t++; printf("Network #%d ", t); for(int u = 1; u <= 1000; u++) if(iscut[u]) { flag = 1; memset(vis, 0, sizeof(vis)); int cnt = 0; vis[u] = 1; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i]; if(!vis[v]) cnt++, dfs1(v); } printf(" SPF node %d leaves %d subnets ", u, cnt); } if(!flag) { puts(" No SPF nodes"); } } return 0; }