并查集
并查集
并查集是用来判断两个元素是否属于同一个集合
即判断他们的根节点是否相同
一.代码与思想
1. 初始化
#define maxn 100
int parent[maxn];
void init(int n)
{
for(int i = 0;i <n;i ++)
{
parent[i] = i;//存放每个节点的节点（或者是双亲节点）
}
}
2.查询根节点
int find(int x)
{
if(parent[x] == x)
return x;
else
return find(parent[x]);
}
3.合并
//合并，把j合并到i中去，就是把j的双亲节点设为i
void merge(int i,int j)
{
parent[find[j]] = find(i);
//此时要合并节点i与j，并不能将他们直接合并
//需要先查找他们各自的老大（根节点）是谁
//将j的根节点合并到i的根节点下方
}
二.路径压缩
集合变为一个长长的链时，查找变得十分麻烦，此时我们需要路径压缩
即每个人的直接根节点就是最上面的根节点
我们判断两个元素是否是同一个集合，看的是他们的 根节点 是否相同
那么我们可以直接把 每个元素的父节点 改为这个集合的代表元素，即根节点
所以我们只要在查找的过程中，把沿途的每个 双亲节点 都设为根节点即可
int find(int x)
{
if(parent[x] == x)
{
return x;
}
else
{
parent[x] = find(parent[x]);
return parent[x];
}
}
或者可以简化为下面的一行版
int find(int x)
{
return x == parent[x] ? x : (parent[x] = find(parent[x]));
}
三. 按秩合并
并查集经过路径压缩后，并不是只有两层的一棵树
最终的结构仍然可能很复杂
1. 思想
为了使树变得更加简洁，我们应该把简单的树往复杂的树上合并
即：把 深度小 的树合并到 深度大 的树中
这样每个元素到根节点的 距离变化的元素个数 最小
2. 按秩合并的做法
1）我们用rank[]数组来记录每个根节点对应的树的深度，如果不是根节点，那么rank[i]表示当前节点作为根节点时的子树的深度
2） 一开始，把所有rank[] = 1，即自己就为一棵树，且深度为1
3）合并的时候，比较两个根节点，把rank较小者合并到较大者中去
2.1 初始化
void init (int t)
{
for(int i = 0;i <n;i ++)
{
parent[i] = i;
rank[i] = 1;
}
}
2.2合并
void merge(int i,int j)
{
int x = find(i),y = find(j);
if(rank[x] < rank[y])
parent[x] = y;
//如果以x作为根节点的子树深度小于以y作为节点的子树的深度
//将x合并到y中
else
parent[y] = x;
if(rank[x] == rank[y] && x != y)
rank[x] ++;
//如果深度相同且根节点不同，以x为节点的子树的深度+1
//即将y合并到x下
}
三.并查集模版
<洛谷 P3367 【模板】并查集 >
#include<bits/stdc++.h>
using namespace std;
int a[200005],b[200005];
int n,m;
int parent[200005],rank[20005];
void init(int num)
{
for(int i = 0;i < num; i++)
{
parent[i] = i;
rank[i] = 1;
}
}
int find(int x)
{
if(parent[x] == x)
return x;
else
{
parent[x] = find(parent[x]);
return parent[x];
}
}
void merge(int x,int y)
{
int rx = find(x);
int ry = find(y);
if(rx != ry)
{
if(rank[rx] < rank[ry])
swap(rx,ry);
parent[ry] = rx;
if(rank[rx] == rank[ry])
rank[rx] ++;
}
}
int main()
{
cin>>n>>m;
init(n);
for(int i = 1; i <= m; i++)
{
int x;
cin>>x>>a[i]>>b[i];
if(x == 1)
merge(a[i],b[i]);
if(x == 2)
{
if(find(a[i]) == find(b[i]))
cout<<'Y'<<endl;
else
cout<<'N'<<endl;
}
}
return 0;
}