首页 > 代码库 > 并查集(基础)
并查集(基础)
并查集， 从这个名字上也可以知道是合并和查找集合的， 它也叫不相交的集的数据结构， 典型的例题有食物链， 来判断有多少个独立的树什么的， 下面一个例题，来简单的解释并查集：一个犯罪团伙一共有n个人， 现在只知道谁跟谁一伙， 来求出一共有多少个团伙， 代码如下：
1 #include <stdio.h> 2 //并查集 3 /*此案例是给定总个数， 从1到n， 然后给定谁和谁是一伙的， 4 输入一个m来确定一个有多少个一伙的， 求出最后一个有几伙*/ 5 int f[1000], n, m, k, sum = 0; 6 //初始化 7 void init() 8 { 9 for(int i = 1; i <= n; i++)10 f[i] = i;11 }12 //找到它的父亲13 int getf(int i)14 {15 if(i != f[i])16 {17 f[i] = getf(f[i]);//路径压缩18 }19 return f[i];20 }21 //合并函数，22 void merge(int i, int j)23 {24 int t1 = getf(i);25 int t2 = getf(j);26 if(t1 != t2)27 {28 f[t2] = t1;29 }30 }31 32 int main()33 {34 // freopen("1.in", "r", stdin);35 scanf("%d ", &n);36 init();37 int m;38 scanf("%d ", &m);39 int x, y;40 for(int i = 1; i <= m; i++)41 {42 scanf("%d %d", &x, &y);43 merge(x, y);44 }45 for(int i = 1; i <= n; i++)46 {47 if(f[i] == i)48 sum++;49 }50 printf("%d\n", sum);51 return 0;52 }
测试数据：
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
结果如下：
并查集(基础)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。