Uva 315

傳送門:https://uva.onlinejudge.org/external/3/315.pdf

tarjan模闆題

其實我才不會告訴你這是我來騙通路量的呢.

代碼

#include <cstdio>   
#include <cstring>   
#include <iostream> 
using  namespace  std;  
int  map[][],low[],dep[];  
int  f[],n,depth,root;  
bool  flag[];   
void  dfs( int  m){  
    dep[m] = depth;  
    low[m] = depth;  
    depth++;  
    flag[m] = true ;  
    int  i,j,k;  
    for (i = ;i <= n; i++){  
        if (map[m][i]){  
            if (!flag[i]){  
                dfs(i);  
                low[m] = min(low[m],low[i]);  
                if (low[i] >= dep[m] && m != )  
                    f[m] ++;  
                else   if (m == ) root ++;  
            }  
            else       
                low[m] = min(low[m],dep[i]);  
        }  
    }  
}  
int  main()  
{  
    int  i,j,k;  
    while (scanf( "%d" ,&n),n){  
        memset(map,,sizeof (map));  
        memset(f,,sizeof (f));  
        memset(low,,sizeof (low));  
        memset(flag,false , sizeof (flag));  
        memset(dep,,sizeof (dep));  
        root  = ;  
        while (scanf( "%d" ,&k),k){  
            while (getchar() != '\n' ){  
                scanf("%d" ,&j);  
                map[k][j] = map[j][k] = ;  
            }  
        }  
        root = ;  
        depth = ;  
        dfs();  
        int  ans = ;  
        if (root > ) ans ++;  
        for (i = ;i <= n; i++)  
            if (f[i]) ans ++;  
        printf("%d\n" ,ans);  
    }  
}