并查集

并查集并查集并查集是用来判断两个元素是否属于同一个集合即判断他们的根节点是否相同一.代码与思想1. 初始化

#define maxn 100int 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;elsereturn find(parent[x]);} 

3.合并

//合并，把j合并到i中去，就是把j的双亲节点设为ivoid 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，即自己就为一棵树，且深度为13）合并的时候，比较两个根节点，把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中elseparent[y] = x;if(rank[x] == rank[y] && x != y)rank[x] ++;//如果深度相同且根节点不同，以x为节点的子树的深度+1 //即将y合并到x下 }

三.并查集模版

#includeusing 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] >n>>m;init(n);for(int i = 1; i >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;elsecout<<'N'<<endl;}}return 0;}