POJ 1523 SPF（求割点）

题意：找出图中所有的割点，然后输出删掉他们之后还剩多少个连通分量。

思路 : v与u邻接，要么v是u的孩子，要么u是v的祖先，（u，v）构成一条回边。

 1 //poj1523
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 
 6 using namespace std ;
 7 
 8 int edge[1010][1010],dfn[1010],low[1010],subnet[1010] ;
 9 int tot,Node ,son;
10 
11 void dfs(int u)
12 {
13     dfn[u] = low[u] = ++tot ;
14     for(int v = 1 ; v <= Node ; v++)
15     {
16         if(edge[u][v])
17         {
18             if(!dfn[v])
19             {
20                 dfs(v) ;
21                 low[u] = min(low[v],low[u]) ;
22                 if(low[v] >= dfn[u])
23                 {
24                     if(u != 1)//非根节点
25                         subnet[u] ++ ;
26                     else son ++ ;
27                 }
28             }
29             else
30             {
31                 low[u] = min(low[u],dfn[v]) ;
32             }
33         }
34     }
35 }
36 
37 void Init()
38 {
39     tot = son = Node = 0;
40     memset(dfn,0,sizeof(dfn)) ;
41     memset(low,0,sizeof(low)) ;
42     memset(subnet,0,sizeof(subnet)) ;
43     memset(edge,0,sizeof(edge)) ;
44 }
45 int main()
46 {
47     int m,n ;
48     int casee = 1 ;
49     while(scanf("%d",&m) && m)
50     {
51         scanf("%d",&n) ;
52         Init() ;
53         Node = max(m,max(n,Node)) ;
54         edge[m][n] = edge[n][m] = 1 ;
55         while(~scanf("%d",&m) && m)
56         {
57             scanf("%d",&n) ;
58             Node = max(m,max(n,Node)) ;
59             edge[m][n] = edge[n][m] = 1 ;
60         }
61 //        if(casee > 1)
62 //            puts("") ;
63         printf("Network #%d
",casee ++) ;
64         dfs(1) ;
65         if(son > 1)
66             subnet[1] = son - 1 ;
67         int flag = 0 ;
68         for(int i = 1 ; i <= Node ; i++){
69             if(subnet[i])
70             {
71                 flag = 1 ;
72                 printf("  SPF node %d leaves %d subnets
",i,subnet[i]+1) ;
73             }
74         }
75         if(!flag)
76             puts("  No SPF nodes") ;
77         puts("") ;
78     }
79     return 0 ;
80 }

View Code