POJ 1144 Network(割点)

テーマリンク:http://poj.org/problem?id=1144
題意:連通する無方向図を与える.割点の個数を求める.
考え方:割点:
(1)DFSは、ノードのdfn値、low値、father値を記録する.
(2)ノードv毎にfatherがuであり、dfn[u]<=low[v]であればuは割点である.ルートノードに余分なサブノードがある場合、ルートノードは分割点です.

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 

 struct node

 {

     int v,next;

 };

 

 node edges[10000];

 int head[105],e;

 int n;

 int dfn[105],low[105],ID,p[105],cut[105];

 

 

 void init()

 {

     memset(head,-1,sizeof(head));

     e=0;

     ID=0;

     memset(cut,0,sizeof(cut));

     memset(dfn,0,sizeof(dfn));

 }

 

 void Add(int u,int v)

 {

     edges[e].v=v;

     edges[e].next=head[u];

     head[u]=e++;

 }

 

 void DFS(int u,int pre)

 {

     ID++;

     dfn[u]=low[u]=ID;

     p[u]=pre;

     int i,v;

     for(i=head[u];i!=-1;i=edges[i].next)

     {

         v=edges[i].v;

         if(!dfn[v])

         {

             DFS(v,u);

             low[u]=min(low[u],low[v]);

         }

         else

         {

             low[u]=min(low[u],dfn[v]);

         }

     }

 }

 

 int main()

 {

     while(scanf("%d",&n),n)

     {

         init();

         int i,u,v;

         while(scanf("%d",&u),u)

         {

             while(getchar()!='
')

             {

                 scanf("%d",&v);

                 Add(u,v);

                 Add(v,u);

             }

         }

         DFS(1,-1);

         int ans=0,x=0;

         for(v=2;v<=n;v++)

         {

             u=p[v];

             if(u==1) x++;

             else if(dfn[u]<=low[v]) cut[u]=1;

         }

         if(x>1) cut[1]=1;

         for(i=1;i<=n;i++) ans+=cut[i];

         printf("%d
",ans);

     }

     return 0;

 }