无向图求割点模板题

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int N=1002; 6  7 int subnets[N]; 8 int dfn[N],low[N]; 9 int count,mun,son,ks;10 11 bool map[N][N];12 bool vis[N];13 14 void init(){15     memset(map,0,sizeof(map));16     for(int i=0;i<=N;++i){17         vis[i]=dfn[i]=low[i]=subnets[i]=0;18     }19     count=1,son=0;20     mun=0;21     dfn[1]=low[1]=vis[1]=1;22 }23 void dfs(int x){24     for(int i=1;i<=mun;i++){25         if(map[x][i]){26             if(!vis[i]){27                 vis[i]=1;28                 dfn[i]=low[i]=++count;29                 dfs(i);30                 low[x]=min(low[x],low[i]);31                 if(low[i]>=dfn[x]){32                     if(x==1)son++;33                     else subnets[x]++;34                 }35             }36             else low[x]=min(low[x],dfn[i]);37         }38     }39 }40 void print(){41     bool yes=0;42     if(son>1)subnets[1]=son-1;43     printf("Network #%d\n",++ks);44     for(int i=1;i<=mun;i++){45         if(subnets[i]){46             yes=1;47             printf("  SPF node %d leaves %d subnets\n",i,subnets[i]+1);48         }49     }50     if(!yes)printf("  No SPF nodes\n");51     printf("\n");52 }53 int main(){54     //freopen("test.txt","r",stdin);55     int a,b;56     ks=0;57     while(scanf("%d",&a)&&a){58         init();59         scanf("%d",&b);60         map[a][b]=map[b][a]=1;61         mun=max(max(b,a),mun);62         while(scanf("%d",&a)&&a){63             scanf("%d",&b);64             map[a][b]=map[b][a]=1;65             mun=max(max(b,a),mun);66         }67         dfs(1);68         print();69     }70     return 0;71 }