并查集代码总结

2019-11-08 02:02:48

字体：大中小

来源：转载

供稿：网友

核心代码：

int find(int x){ while(x != root[x])/*循环寻找x对应根的值*/ { x = root[x]; } return x;}void unio(int a, int b)/*合并a所在的树的根，和b所在的树的根*/{ int x, y; x = find(a);/*求a的根*/ y = find(b);/*求b的根*/ if(x != y) { root[y] = x;/*让y的根等于x*/ }}

题目：小鑫的城堡http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestPRoblem/cid/2014/pid/2798.html

#include<stdio.h>#include<stdlib.h>#include<string.h>int root[100555], flag;int house[100555];int find(int x){ while(x != root[x]) { x = root[x]; } return x;}void unio(int a, int b){ int x, y; x = find(a); y = find(b); if(x != y) { root[y] = x; } else flag = 0;//判断是否回路}int max1(int a, int b){ if(a < b) return b; else return a;}int main(){ int m, a, b, i, max, num; while(~scanf("%d", &m)) { max = 0; num = 0; memset(house, 0, sizeof(house)); flag = 1; for(i = 1; i <= 100005; i++)//初始化根 root[i] = i; for(i = 0; i < m; i++) { scanf("%d %d", &a, &b); if(max < max1(a, b))//找出最大房间号 max = max1(a, b); house[a]++; house[b]++; unio(a, b);//合并 } for(i = 1; i <= max; i++) { if(house[i]) num++;//统计房间数 } if(flag && num == m + 1) printf("Yes/n");//图满足房间数等于路径数加一 && 不允许有回路 else printf("No/n"); } return 0;}

上一篇：jstl--I18N标签库

下一篇：【数据结构】栈和队列的面试题