targan算法。

1 # include 
     
       2 # include 
      
        3  4 # define N (1000 + 5) 5  6 int n, son, tmpdfn; 7 int low[N], dfn[N], subnets[N]; 8 char g[N][N]; 9 10 int Min(int x, int y)11 {12     return x
       
        = dfn[u])26             {27                 if (u != r) ++subnets[u];28                 else ++son;29             }30         }31         else32             low[u] = Min(low[u], dfn[v]);33     }34 }35 36 void init(void)37 {38     tmpdfn = 0;39     memset(low+1, 0, sizeof(int)*n);40     memset(dfn+1, 0, sizeof(int)*n);41     memset(subnets+1, 0, sizeof(int)*n);42 }43 44 void solve(void)45 {46     bool find = false;47     for (int i = 1; i <= n; ++i) if (!dfn[i])48     {49         son = 0;50         tarjan(i, i);51         if (son > 1) subnets[i] = son - 1;52     }53     for (int i = 1; i <= n; ++i)54     {55         if (subnets[i])56         {57             find = true;58             printf("\n  SPF node %d leaves %d subnets", i, subnets[i]+1);59         }60     }61     if (find == false)62         printf("\n  No SPF nodes");63 }64 65 int read_graph(void)66 {67     n = 0;68     memset(g, 0, sizeof(g));69     int x, y;70     scanf("%d", &x);71     if (x == 0) return 0;72     do73     {74         scanf("%d", &y);75         g[x][y] = g[y][x] = 1;76         if (x > n) n = x;77         if (y > n) n = y;78     }while (scanf("%d", &x), x);    79     return 1;80 }81 82 int main()83 {    84     int icase = 0;85     while (read_graph())86     {87         if (icase != 0) printf("\n\n");88         printf("Network #%d", ++icase);89         init();90         solve();91     }92 }
       
      
     

注意n=1的情况。