生活中有很多连通性问题。解决方案——并查集。
1. quickFind算法
并查集的第一个算法：Quick-Find
算法思想：
- 基于染色思想，一开始每个人都是自己一个颜色
- 连接两个点时，把两个点设置成一个颜色。
- 如果两个点颜色一样，说明是一伙的，否则不是
算法优劣：
联通判断：O(1)
合并操作：O(n)
优化思考：
- quick-find算法的联通判断很快，合并操作很慢
- 本质上就是知道谁和谁的颜色一样
- 联通的点都指向一个节点
- 合并操作是让一棵树中的所有点指向另一棵数的根是否有优化空间？
编码设计：（C语言）
#include<stdio.h>
#include<stdlib.h>
// 并查集的基础结构——color数组+size大小
typedef struct UnionSet {
int *color; // 存储每个人的颜色
int size; // 代表有多少个人
}UnionSet;
// 并查集的初始化
UnionSet *initSet(int n) {
UnionSet *u = (UnionSet *)malloc(sizeof(UnionSet));
u->color = (int *)malloc(sizeof(int) * n);
u->size = n;
for(int i=0;i<u->size;i++) u->color[i] = i; // 初始化每个人都是自己一个颜色
return u;
}
// 内存的释放
void freeSet(UnionSet *u) {
if(!u) return;
free(u->color); // 释放顺序：先释放里面的零部件，后释放整个并查集
free(u);
return ;
}
// 通过下标寻找当前节点在并查集中的所属颜色。
int find(UnionSet *u, int idx){
return u->color[idx];
}
// 完成合并操作
int merge(UnionSet *u,int a,int b) {
if(find(u,a)==find(u,b)) return 0;
int acolor = find(u,a); // 获取a的颜色
int i;
for(i=0;i<u->size;i++){ // 把所有是a的颜色的人改为b的颜色——将a合并到b中
if(find(u,i) == acolor){
u->color[i] = u->color[b];
}
}
return 1;
}
int main(){
int n,m; // n为节点的个数， m代表边的个数。
scanf("%d%d", &n,&m);
UnionSet *u = initSet(n + 1);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
switch(a){
case 1: // 如果是1就合并b,c
merge(u,b,c);
break;
case 2: // 如果是2，就输出b和c的关系
printf("%s\n", find(u,b)==find(u,c)?"Yes":"No");
break;
}
}
freeSet(u);
return 0;
}
C++版：
#include<iostream>
#include<cstdio>
using namespace std;
class UnionSet {
public:
UnionSet(int n) : color(new int[n]), size(n) {
for (int i = 0; i < n; i++) color[i] = i;
}
int find(int ind) {
return color[ind];
}
int merge(int a,int b) {
int fa = find(a), fb = find(b);
if(fa == fb) return 0;
for(int i=0;i<size;i++){
if(find(i) == fa) color[i] = fb;
}
return 1;
}
~UnionSet() {
delete[] color;
}
int *color;
int size;
};
int main() {
int n,m;
cin >> n >> m;
UnionSet u(n + 1);
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
switch(a) {
case 1: {
u.merge(b, c);
break;
}
case 2: {
// 判断是否联通
printf("%s\n", u.find(b) == u.find(c)?"Yes":"No");
break;
}
}
}
return 0;
}
样例输入
6 5
1 1 2
2 1 3
1 2 4
1 4 3
2 1 3
样例输出
No
Yes
2. quickUnion算法
- 一开始每个人都是自己的一个队友，相当于没有队友。
- 连接你和你的队友时，让他没有队友的队友，作为你没有队友的队友，的队友
- 如果两个人，没有队友的队友，是一个人，说明他们是队友。
class UnionSet {
public:
UnionSet(int n) : father(new int[n]), size(n) {
for(int i=0;i<n;i++){
father[i]=i;
}
}
int find(int ind) {
if(father[ind] == ind) return ind;
return find(father[ind]);
}
void merge(int a,int b) {
int fa = find(a), fb = find(b);
if(fa ==fb) return ;
father[fa] = fb;
return ;
}
int *father;
int size;
~UnionSet(){
delete[] father;
}
};
3.weighted quickUnion算法原理
如果一个帮派的人数大于另一个帮派的人数。那么当这两个帮派合并的时候，人数少的一方自然要认人数多的一方。weighted quickUnion算法也是如此。
class UnionSet {
public:
UnionSet(int n) : father(new int[n]), len(new int[n]), size(n) {
for(int i=0;i<size;i++) {
father[i]=i;
len[i]=i;
}
}
int find(int ind) {
if(father[ind] == ind) return ind;
return find(father[ind]);
}
int merge(int a,int b) {
int fa=find(a), fb=find(b);
if(fa==fb) return 0;
if(len[fa]>len[fb]){
father[fb]=fa;
len[fa]+=len[fb];
}else{
father[fa]=fb;
len[fb]+=len[fa];
}
return 1;
}
~UnionSet() {
delete[] len;
delete[] father;
}
int *father, *len, size; // 增加一个变量len
};
4. 路径压缩代码：
在寻找父亲find()的路上，如果找到了最终的父亲，那么之前一路以来的所有孩子都可以直接认它为父节点。这样当再次查找的时候就可以简单很多。
class UnionSet {
public:
UnionSet(int n) : father(new int[n]), size(n) {
for(int i=0;i<n;i++){
father[i]=i;
}
}
// 路径压缩核心代码：
int find(int ind) {
return father[ind] = father[ind]==ind?ind:find(father[ind]);
}
void merge(int a,int b) {
int fa = find(a), fb = find(b);
if(fa ==fb) return ;
father[fa] = fb;
return ;
}
int *father;
int size;
~UnionSet(){
delete[] father;
}
};
