HDU1272

http://acm.split.hdu.edu.cn/showproblem.php?pid=1272

对于这道题，只要找出形成的图是不是连通无环的图即可。即是判断输入的两个点是否来自同一个父亲结点。还要注意不要忘记这个图一定是互相连通的。另外注意当输入两个0的时候也是输出Yes

 #include<stdio.h>

 #include<algorithm>

 #include<iostream>

 #include<string.h>

 using namespace std;

 const int M=;

 int fa[M],vis[M];

 int fin(int x)

 {

     return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);

 }

 int unin(int x,int y){

 return fa[fin(x)]=fin(y);

 }

 int main()

 {

     int a,b;

     while(~scanf("%d%d",&a,&b)){

         if(a==-&&b==-)break;

         if(a==&&b==){

           puts("Yes");

             continue;

         }

         int flag=;

         for(int i=;i<M;i++){

             fa[i]=i;

         }

         memset(vis,,sizeof(vis));

         unin(a,b);

         vis[a]=vis[b]=;

         while(~scanf("%d%d",&a,&b)){

             if(a==&&b==)break;

             if(fin(a)==fin(b))flag=;

             else unin(a,b);

             vis[a]=vis[b]=;

         }

         if(!flag)puts("No");

         else {for(int i=;i<M;i++)

             if(vis[i]&&fa[i]==i)

                 flag++;

          if(flag==)puts("Yes");

         else puts("No");

         }

     }

 return ;

 }

对于输入输出数据多的代码，要用scanf和printf，此题用cin和cout就会超时。