无向图割顶 Network

原题：Network

原题大意

求割顶的模板题。

程序代码

#include <iostream>  
#include <cstdio>  
#include <vector>  
#include <sstream>  
#include <cstring>  
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 1e5+5;
vector<int> G[maxn];
int dfs_clock, iscut[maxn], pre[maxn], low[maxn];
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]){
                iscut[u] = true;
            }
        }
        else if(pre[v] < pre[u] && v != fa){
            lowu = min(pre[v], lowu);
        }
    }
    if(fa < 0 && child == 1) iscut[u] = false;
    return lowu;
}
void find_cut(int n){
    mem(pre,0);
    mem(iscut,0);
    dfs_clock = 0;
    for(int i = 1; i <= n; i++)
        if(!pre[i]) dfs(i,-1);
}
int main(){

    int n;
    while(scanf("%d",&n)!=EOF&&n){  

        for(int i = 0; i <= n; i++)G[i].clear();
        getchar();  
        string tmp;  
        while(getline(cin,tmp)){  

            int l,r;  
            stringstream ss(tmp);  
            ss>>l;  
            if(!l) break;  
            while(ss>>r){  
                G[l].push_back(r);  
                G[r].push_back(l);  
            }  
        }
        find_cut(n);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            if(iscut[i])ans++;
        }
        cout <<ans << "\n";

    }  
    return 0;
}