68
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");
}
}最後更新：2017-08-13 22:33:42