Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 25010 Accepted Submission(s): 7683
6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0 3 8 6 8 6 4 5 3 5 6 5 2 0 0 -1 -1
Yes Yes No
这也是一道并查集的题
解题思路:题目意思是找到判断是不是连通无环的图。
1。判断成环:读入过程中,合并集合的时候,如果,当前读入的两个
元素属于同一个集合,那么肯定是No。
2。判断连通:只要判断根节点数为1即可。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<sstream> #include<cmath> using namespace std; #define f1(i, n) for(int i=0; i<n; i++) #define f2(i, n) for(int i=1; i<=n; i++) #define f3(i, n) for(int i=n; i>=1; i--) #define f4(i, n) for(int i=1; i<n; i++) #define M 100500 int f[M]; int flag; int sum; int find (int x) //并查集的find { return f[x] == x ? x : f[x] = find(f[x]); } void make(int a, int b) { int x = find(a); int y = find(b); if( x==y ) //如果是同一集合,即产生环,则标记 flag = 1; else f[y] = x; } int main() { int a, b; while( 1 ) { memset(f, 0, sizeof(f)); flag = 0; sum = 0; while(scanf("%d%d", &a, &b) &&a &&b) { if( a==-1 && b==-1 ) return 0; if(f[a]==0) f[a] = a; if(f[b]==0) f[b] = b; make(a, b); } f4(i, M) if(f[i]==i) sum++; //printf("%d^^^%d", sum, flag); if(sum>1 || flag==1)//有环或断根节点大于1则是No printf("No\n"); else printf("Yes\n"); } return 0; }
注意:当输入的这组数据只有 0 0 时,依然是满足条件的,即应输出 "Yes"
HDU 1272: 小希的迷宫(并查集),布布扣,bubuko.com
原文:http://blog.csdn.net/u013487051/article/details/37767453