首页 > 代码库 > HDU1272

HDU1272

2024-08-11 10:37:26   217人阅读

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

技术分享

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

技术分享
 1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 using namespace std; 6 const int M=100015; 7 int fa[M],vis[M]; 8 int fin(int x) 9 {10     return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);11 }12 int unin(int x,int y){13 return fa[fin(x)]=fin(y);14 }15 int main()16 {17     int a,b;18     while(~scanf("%d%d",&a,&b)){19         if(a==-1&&b==-1)break;20         if(a==0&&b==0){21           puts("Yes");22             continue;23         }24         int flag=1;25         for(int i=0;i<M;i++){26             fa[i]=i;27         }28         memset(vis,0,sizeof(vis));29         unin(a,b);30         vis[a]=vis[b]=1;31         while(~scanf("%d%d",&a,&b)){32             if(a==0&&b==0)break;33             if(fin(a)==fin(b))flag=0;34             else unin(a,b);35             vis[a]=vis[b]=1;36         }37         if(!flag)puts("No");38         else {for(int i=0;i<M;i++)39             if(vis[i]&&fa[i]==i)40                 flag++;41          if(flag==2)puts("Yes");42         else puts("No");43 44         }45     }46 return 0;47 }
View Code

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

HDU1272


联系
我们