poj1144 割顶

#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;
    }