poj 1523--SPF

题意：问删除某个点是否形成多个网络
思路：求割点
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=1002;
 6 
 7 struct node{
 8     int to,next;
 9 }e[N*N];
10 
11 int head[N],tot;
12 int dfn[N],low[N],a[N];
13 int indexx;
14 int n;
15 int tt;
16 
17 void init(){
18     memset(head,-1,sizeof(head));
19     memset(dfn,0,sizeof(dfn));
20     memset(low,0,sizeof(low));
21     indexx=0;
22     n=0;
23     tt=0;
24 }
25 
26 void add(int u,int v){
27     e[tot].to=v;
28     e[tot].next=head[u];
29     head[u]=tot++;
30 }
31 
32 void dfs(int u){
33     dfn[u]=low[u]=++indexx;
34     for(int i=head[u];i!=-1;i=e[i].next){
35         int v=e[i].to;
36         if(!dfn[v]){
37             dfs(v);
38             low[u]=min(low[u],low[v]);
39             if(dfn[u]<=low[v]) {
40                 a[u]++;
41             }
42         }
43         else low[u]=min(low[u],dfn[v]);
44     }
45 }
46 
47 int main(){
48     init();
49     int t=1;
50     int x,y;
51     while(scanf("%d",&x)){
52         if(x==0) break;
53         init();
54         scanf("%d",&y);
55         add(x,y);add(y,x);
56         n=max(max(x,y),n);
57         while(scanf("%d",&x)&&x){
58             scanf("%d",&y);
59             add(x,y);add(y,x);
60             n=max(max(y,x),n);
61         }
62         for(int i=2;i<=n;i++) a[i]=1;
63         a[1]=0;
64         dfs(1);
65        printf("Network #%d
",t++);
66               for(int i=1;i<=n;i++)
67               if(a[i]>1)
68               {
69                        printf("  SPF node %d leaves %d subnets
",i,a[i]);
70                        tt=1;
71               }
72            if(!tt)printf("  No SPF nodes
");
73        printf("
");
74     }
75     return 0;
76 }