并查集-模板（自用）

并查集模板题目--对应题目为洛谷的并查集模板（搜一下就可以了）

#include<iostream>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int maxn=200005;
int Rank[maxn];  //用于表示深度
int parent[maxn]; //并查集模拟树用的
int n,m;
int find_root(int x) { //查询
 while(x!=parent[x]) {
  x=parent[x];
 }
 return x;
}
void union_root(int x,int y) { //合并 
 int x_root=find_root(x);
 int y_root=find_root(y);
 if(Rank[x_root]>Rank[y_root]) {
  parent[y_root]=x_root;
 } else if(Rank[y_root]>Rank[x_root]) {
  parent[x_root]=y_root;
 } else {
  parent[x_root]=y_root;
  Rank[y_root]++;
 }
}
int main() {
 hh;
 cin>>n>>m;
 for(int i=1; i<=n; i++) {
  parent[i]=i;
  Rank[i]=0;
 }
 while(m--) {
  int z,x,y;
  cin>>z>>x>>y;
  if(z==1) {
   union_root(x,y);
  } else if(z==2) {
   if(find_root(x)==find_root(y)) {
    puts("Y");
   } else {
    puts("N");
   }
  }
 }
 return 0;
}

同时还有一个自己测试用的并查集模板：

#include<iostream>
#include<stdlib.h>
using namespace std;
const int VERTICES=6;
void initialise(int parent[],int rank[]) {
 for(int i=0; i<VERTICES; i++) {
  parent[i]=-1;
  rank[i]=0;
 }
}
int find_root(int x,int parent[]) {
 int x_root=x;
 while(parent[x_root]!=-1) {
  x_root=parent[x_root];
 }
 return x_root;
}
/* 1 --- union successfully , 0 --- filed */
int union_vertices(int x,int y,int parent[],int rank[]) {
 int x_root=find_root(x,parent);
 int y_root=find_root(y,parent);
 if(x_root==y_root) {
  return 0; //false
 } else {
  if(rank[x_root]>rank[y_root]) {
   parent[y_root]=x_root;
  } else if(rank[y_root]>rank[x_root]) {
   parent[x_root]=y_root;
  } else {
   parent[x_root]=y_root;
   rank[y_root]++;
  }
  //not use rank
  //parent[x_root]=y_root;
  return 1; //true
 }
}
int main() {
 int parent[VERTICES]= {0};
 int rank[VERTICES]= {0};
 const int N=6;
 int edges[N][2]= {
  {0,1},{1,2},{1,3},{2,4},{3,4},{2,5}
 };
 initialise(parent,rank);
 for(int i=0; i<N; i++) {
  int x=edges[i][0];
  int y=edges[i][1];
  if(union_vertices(x,y,parent,rank)==0) {
   cout<<"Cycle detected!"<<endl;
   //printf("Cycle detected!");
   exit(0);
  }
 }
 cout<<"No cycles found."<<endl;
 return 0;
}

内容差不多的....

原理可以百度，一大把的