29
poj1144 割頂
如果節點沒被訪問過才child++#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
vector<int> g[211];
int dfs_clock, n, pre[211], cut[211];
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);
lowu = min(lowu, lowv);
if (lowv >= pre[u]) cut[u] = 1;
}else
if (v != fa && pre[u] > pre[v]) lowu = min(lowu, pre[v]);
}
if (fa < 0) cut[u] = child > 1 ? 1 : 0;
return lowu;
}
int main(){
while (cin>>n && n){
dfs_clock = 0;
for (int i = 1; i <= 100; i++) g[i].clear();
memset(pre, 0, sizeof(pre));
memset(cut, 0, sizeof(cut));
int u, v;
while (cin>>u && u){
while (getchar() != '\n'){
cin>>v;
g[u].push_back(v);g[v].push_back(u);
}
}
if (n < 3) {
cout<<"0\n";
continue;
}
dfs(1, -1);
int ans = 0;
for (int i = 1; i <= n; i++) ans += cut[i];
cout<<ans<<'\n';
}
return 0;
}
最後更新：2017-08-13 22:35:20