【简介】 并查集(Union Find)是一种用于管理分组的数据结构。它具备两个操作：(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组。 核心代码： 1.查询代码
int find(int k){//寻找根节点 if(node[k].father==k) return k; else{ node[k].father=find(node[k].father);//路径压缩，一路上每次函数返回时顺便把其指向的父节点直接改为根节点 ////即直接把这个点挂到根节点上 return node[k].father; } }2.合并代码
void merge(int u,int v)//uX，v为Y { u=find(u);v=find(v);//u，v为根节点 if(node[u].rank>node[v].rank)//如果u的子节点深度大于v的话，u为v的根节点 node[v].father=u; else{ node[u].father=v;//同上 if(node[u].rank==node[v].rank)//如果深度相等 node[v].rank++;//v的深度+1； } }模板题： P3367 【模板】并查集 代码：
#include<cstdio> #include<cstdlib> using namespace std; #define INF 10000+5 #define INF2 200000+5 int n,m; struct Node{//写大写是为了避免与之后的node重复 //int data; int rank;//rank代表这一个节点和他的所有子节点的深度 int father; }node[INF+1]; int get_bigfather(int k)//寻找根节点 ——一般是在这里加上路径压缩的 { if(node[k].father==k) return k; else { node[k].father=get_bigfather(node[k].father);//路径压缩——一路上每次函数返回时顺便把其指向的父节点直接改为根节点 //即直接把这个点挂到根节点上 return node[k].father; } } void merge(int u,int v) { u=get_bigfather(u); v=get_bigfather(v); if(node[u].rank>node[v].rank) node[v].father=u; else { node[u].father=v; if(node[u].rank==node[v].rank) node[v].rank++; } } int main() { scanf("%d%d",&n,&m);//n个元素，m个操作 for(int i=1;i<=n;i++)//初始化，自己的父亲一开始是自己 node[i].father=i; for(int i=1;i<=m;i++) { int temp,u,v; scanf("%d%d%d",&temp,&u,&v); if(temp==1)//合并 merge(u,v); else { if(get_bigfather(u)==get_bigfather(v)) printf("Y\n"); else printf("N\n"); } } return 0; }