首页 > 代码库 > 利用并查集判断一个无向图是否成树
利用并查集判断一个无向图是否成树
hdu 1272
利用并查集方法,找到各点的根节点。
几点注意:
一、树:1.无环 2.根节点入度为0,其余入度为1
判断依据:
1.若两个点的根节点相同(这两个点是父子关系),则形成环。
2.若所有点中只有一个点的根节点是他本身,则根节点入度为0。
二、
1. 0 0 :空树也是一颗树。
1 #include<iostream> 2 #include<algorithm> 3 #define Max 100005 4 using namespace std; 5 6 int f[Max]; 7 8 int root(int i) 9 { 10 if(f[i] == i) 11 return i; 12 else 13 return root(f[i]); 14 } 15 int huan; 16 void U(int a,int b) 17 { 18 int f1,f2; 19 f1 = root(a); 20 f2 = root(b); 21 if(f1 != f2) 22 { 23 f[f1] = f2; 24 } 25 else 26 { 27 huan = 1;//子环 28 } 29 } 30 int main() 31 { 32 int n,m,i,j,k,t; 33 while(~scanf("%d %d",&n,&m)) 34 { 35 huan = 0; 36 memset(f,0,sizeof(f)); 37 if(m == -1 && n == -1) 38 break; 39 else if(m == 0 && n == 0) 40 { 41 printf("Yes\n"); 42 continue; 43 } 44 else 45 { 46 f[n] = n; 47 f[m] = m; 48 U(n,m); 49 } 50 while(~scanf("%d %d",&n,&m)) 51 { 52 if(n == 0 && m == 0) 53 break; 54 else 55 { 56 if(f[n] == 0) 57 { 58 f[n] = n; 59 } 60 if(f[m] == 0) 61 { 62 f[m] = m; 63 } 64 U(n,m); 65 } 66 } 67 if(huan) 68 { 69 printf("No\n"); 70 continue; 71 } 72 k = 0; 73 for(i = 0;i < Max;i ++) 74 { 75 if(f[i] == i && f[i] != 0) //只有一个点的根节点是他本身 76 k ++; 77 } 78 if(k == 1) 79 printf("Yes\n"); 80 else 81 printf("No\n"); 82 } 83 return 0; 84 }
利用并查集判断一个无向图是否成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。