由如下几部分构成：
集合 : parent , size(代表深度或融合大小，大的融合小的) 变量 ：n(并查集节点总数) ， setCount(当前连通变量总数) 方法 ：

  • 构造函数初始化（iota）
  • find
  • merge

并查集算法步骤：

  1. 确定并查集数据是什么？
    1. 例子：比如说从A点到达B点，说明应存取position。当connected(A,B)时，说明存在路径到达AB
  2. 确定按什么顺序合并?
    1. 最短路径（最大值-最小值）例子
      1. 将所有路径按从小到大的顺序排列
      2. 根据路径权值顺序，将位置加入并查集，知道满足connect(A,B)条件
    2. 下雨游泳例子
      1. 将当前高度按从小到大顺序排列
      2. 根据高度从小到大遍历，将位置加入并查集，直到connect(A,B)满足

并查集基础版本

初始化

假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

  1. int fa[MAXN];
  2. inline void init(int n)
  3. {
  4.     for (int i = 1; i <= n; ++i)
  5.         fa[i] = i;
  6. }

查询（根节点/代表元素）

根节点的标志就是父节点是本身

  1. int find(int x){
  2.     if(fa[x]==x){
  3.         return x;
  4.     }else{
  5.         return find(fa[x]);
  6.     }
  7. }

合并

先找到两个集合的代表元素（根节点），然后将前者的父节点设为后者即可

  1. inline void merge(int i,int j){
  2.     fa[find(i)]=find(j);
  3. }

优化方案

路径压缩（查询过程中进行）

在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。

  1. int find(x){
  2.     if(fa[x]==x){
  3.         return x;
  4.     }else{
  5.         fa[x]=find(fa[x]);   //将父节点设置为根节点
  6.         return fa[x];
  7.     }
  8.     /* 一行 */
  9.     return fa[x]==x ? x : (fa[x]=find(fa[x]));    
  10. }

按秩（不同合集的深度）合并

秩小的往秩大的合并

  1. int fa[MAXN];
  2. int rank[MAXN];
  3. inline void init(int n){
  4.     for(int i=1;i<=n;i++){
  5.         fa[i]=i;
  6.         rank[i]=1;
  7.     }
  8. }
  10. inline void merge(i,j){
  11.     int x=find(i),y=find(j);
  12.     if(rank[x]<=rank[y]){
  13.         fa[x]=y;
  14.     }else{
  15.         fa[y]=x;
  16.     }
  17.     if(rank(x)==rank(y) && x!=y){
  18.         rank[y]++;                       /*深度相同且根节点不同，合并的树深度加一*/
  19.     }
  20. }

C++11模板

  1. class UnionFind {
  2. public:
  3.     vector<int> parent;
  4.     vector<int> size;
  5.     int n;
  6.     /* 当前【连通分量】数 */
  7.     int setCount;
  9. public:
  10.     UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
  11.         iota(parent.begin(), parent.end(), 0);/*itoa 自增+1*/
  12.     }
  14.     int findset(int x) {
  15.         return parent[x] == x ? x : (parent[x] = findset(parent[x]));
  16.     }
  18.     bool unite(int x, int y) {
  19.         x = findset(x);
  20.         y = findset(y);
  21.         if (x == y) {
  22.             return false;
  23.         }
  24.         if (size[x] < size[y]) {
  25.             swap(x, y);
  26.         }
  27.         parent[y] = x;                /*将小秩合并到大秩序*/
  28.         size[x] += size[y];
  29.         --setCount;                    /*合并后【连通分量数】-1*/
  30.         return true;
  31.     }
  33.     bool connected(int x, int y) {
  34.         x = findset(x);
  35.         y = findset(y);
  36.         return x == y;
  37.     }
  38. };
  40. /* 合理范围内也需要对基础款进行魔改 ————  婴儿名字 */
  41. class UnionFind{
  42. public:
  43.     unordered_map<string,string> parent_;
  44.     unordered_map<string,int> size_;
  45.     int n_;    /* 当前连通变量数 */
  46. public:
  47.     UnionFind(int _n):
  48.         n_(_n){
  49.         }
  50.     string find(string x){
  51.         if(parent_.find(x)==parent_.end()){
  52.             ++n_;
  53.             parent_[x]=x;
  54.             return x;
  55.         }
  56.         return x==parent_[x] ? x : (parent_[x]=find(parent_[x]));
  57.     }
  58.     void merge(string i,string j){
  59.         string x=find(i),y=find(j);
  60.         if(x==y){
  61.             return;
  62.         }
  63.         if(x<y){
  64.             swap(x,y);
  65.         }
  66.         /*字典序最小的为根元素*/
  67.         parent_[x]=y;
  68.         size_[y]+=size_[x];
  69.         /* 被合并的规模至0，便于输出答案 */
  70.         size_[x]=0;
  71.         n_--;
  72.     }
  73.     bool connected(string i,string j){
  74.         return find(i)==find(j);
  75.     }
  76.     int getSize(string x){
  77.         return size_[x];
  78.     }
  79. };

例题详解

亲戚关系(基础)

题目背景 若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。 题目描述 规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 输入格式 第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。 以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。 接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。 输出格式

P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。

  1. const int MAXN=5005;
  2. int fa[MAXN];
  3. int rank[MAXN];
  4. inline void init(){
  5.     for(int i=0;i<n;i++){
  6.         fa[i]=i;
  7.         rank[i]=1;
  8.     }
  9. }
  10. int find(x){
  11.     return fa[x]==x ? x : (fa[x]=find(fa[x]));
  12. }
  13. int merge(i,j){
  14.     int x=find(i),y=find(j);
  15.     if(rank[x]<=rank[y]){
  16.         fa(x)=y;
  17.     }else{
  18.         fa(y)=x;
  19.     }
  20.     if(rank[x]==rank[y] && x!=y){
  21.         rank[y]++;
  22.     }
  23. }
  24. int main(){
  25.     int n,m,p;
  26.     cin>>n>>m>>p;
  27.     init(n);
  28.     for(int i=0,x,y;i<m;i++){
  29.         cin>>x>>y;
  30.         merge(x,y);
  31.     }
  32.     for(int i=0,x,y;i<p;i++){
  33.         cin>>x>>y;
  34.         printf("%s\n",find(x)==find(y)? "YES" : "NO");
  35.     }
  36.     return 0;
  37. }

奶酪（提高）

题目描述

现有一块大奶酪，它的高度为 并查集 - 图1 ，它的长度和宽度我们可以认为是无限大的，奶酪中间有许多半径相同的球形空洞。我们可以在这块奶酪中建立空间坐标系，在坐标系中， 奶酪的下表面为 并查集 - 图2 ，奶酪的上表面为 并查集 - 图3 。

现在，奶酪的下表面有一只小老鼠 Jerry，它知道奶酪中所有空洞的球心所在的坐标。如果两个空洞相切或是相交，则 Jerry 可以从其中一个空洞跑到另一个空洞，特别地，如果一个空洞与下表面相切或是相交，Jerry 则可以从奶酪下表面跑进空洞；如果一个空洞与上表面相切或是相交，Jerry 则可以从空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道，在 不破坏奶酪 的情况下，能否利用已有的空洞跑到奶酪的上表面去?

空间内两点 并查集 - 图4 、 并查集 - 图5 的距离公式如下：

并查集 - 图6

输入格式

每个输入文件包含多组数据。

的第一行，包含一个正整数 并查集 - 图7 ，代表该输入文件中所含的数据组数。

接下来是 并查集 - 图8 组数据，每组数据的格式如下： 第一行包含三个正整数 并查集 - 图9 和 并查集 - 图10 ，两个数之间以一个空格分开，分别代表奶酪中空 洞的数量，奶酪的高度和空洞的半径。

接下来的 并查集 - 图11 行，每行包含三个整数 并查集 - 图12 ，两个数之间以一个空格分开，表示空 洞球心坐标为 并查集 - 图13 。

输出格式

并查集 - 图14行，分别对应并查集 - 图15组数据的答案，如果在第 并查集 - 图16 组数据中，Jerry 能从下表面跑到上表面，则输出Yes，如果不能，则输出No（均不包含引号）。

并查集 - 图17
可以将所有空洞划分若干个集合，一旦两个空洞相切或者相交，则将其放入同一个集合中。
还可以划分两个特殊集合，分别为顶部和底部，显然其执行逻辑和空洞相同。若相切或者相交，则放入同一集合。
题目可转化为判断顶部和底部是否在同一集合中。
顶部和底部相较，则说明有一个通路存在。

  1. const int MAXN=1005;
  2. int fa[MAXN],rank[MAXN];
  3. using POS=int[3];
  4. vector<POS> _pos;
  5. /*
  6. init find merge
  7. */
  8. bool isConnected(int[] _p1,int[] _p2,int r){
  9.     return (pow(_p1[0]-_p2[0],2)+pow(_p1[1]-_p2[1],2)+pow(_p1[2]-_p2[2],2))<=pow(2*r,2);
  10. }
  11. int main(){
  12.     int T;
  13.     cin>>T;
  14.     for(int i=0;i<T;i++){
  15.         int n,h,r;
  16.         cin>>n>>h>>r;
  17.         init(n);
  18.         fa[1001]=1001;
  19.         fa[1002]=1002;
  20.         for(int i=0;i<n;i++){
  21.             cin>>_pos[i][0]>>_pos[i][1]>>_pos[i][2];
  22.             if(_pos[i][2]<=r)
  23.                 merge(i,1001);
  24.             if(h-_pos[i][2]<=r);
  25.                 merge(i,1002);
  26.         }
  27.         for(int i=0;i<n;i++)
  28.             for(int j=i+1;j<n;j++){
  29.                 if(isConnected(_pos[i],_pos[j])){
  30.                     merge(i,j);
  31.                 }
  32.             }
  33.         printf("%s\n",find(1001)==find(1002) ? "yes":"no");
  34.     }
  35. }

最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。


思路：

将mn个节点放入并查集中，并实时维护其连通性。当某个集合中同时存在0 和m*n-1（其代表节点相同）时，便说明此路径是合法路径。
由于目标是寻找体力最小的一条路径,故将所有路径从小到大进行排列，当合并的新路径权值为v时，且满足上述条件时，则说明v为该路径的最小体力值，返回该值即可。

面试题 17.07. 婴儿名字

每年，政府都会公布一万个最常见的婴儿名字和它们出现的频率，也就是同名婴儿的数量。有些名字有多种拼法，例如，John 和 Jon 本质上是相同的名字，但被当成了两个名字公布出来。给定两个列表，一个是名字及对应的频率，另一个是本质相同的名字对。设计一个算法打印出每个真实名字的实际频率。注意，如果 John 和 Jon 是相同的，并且 Jon 和 Johnny 相同，则 John 与 Johnny 也相同，即它们有传递和对称性。

在结果列表中，选择 字典序最小 的名字作为真实名字。

  1. class UnionFind{
  2. public:
  3.     unordered_map<string,string> parent_;
  4.     unordered_map<string,int> size_;
  5.     int n_;
  6. public:
  7.     UnionFind(int _n):
  8.         n_(_n){
  9.         }
  10.     string find(string x){
  11.         if(parent_.find(x)==parent_.end()){
  12.             ++n_;
  13.             parent_[x]=x;
  14.             return x;
  15.         }
  16.         return x==parent_[x] ? x : (parent_[x]=find(parent_[x]));
  17.     }
  18.     void merge(string i,string j){
  19.         string x=find(i),y=find(j);
  20.         if(x==y){
  21.             return;
  22.         }
  23.         if(x<y){
  24.             swap(x,y);
  25.         }
  26.         /*字典序最小的为根元素*/
  27.         parent_[x]=y;
  28.         size_[y]+=size_[x];
  29.         size_[x]=0;
  30.         n_--;
  31.     }
  32.     bool connected(string i,string j){
  33.         return find(i)==find(j);
  34.     }
  35.     int getSize(string x){
  36.         return size_[x];
  37.     }
  38. };
  40. class Solution {
  41. public:
  42.     vector<string> trulyMostPopular(vector<string>& names, vector<string>& synonyms) {
  43.         int N=names.size();
  44.         UnionFind unionFind_(N);
  45.         for(const auto &str:names){
  46.             int i=str.find('(');
  47.             int j=str.find(')');
  48.             string name=str.substr(0,i);
  49.             unionFind_.parent_[name]=name;
  50.             int cnt=atoi(str.substr(i+1,j-i-1).c_str());
  51.             unionFind_.size_[name]=cnt;
  52.         }
  53.         for(const auto &str:synonyms){
  54.             int i=str.find(',');
  55.             string left=str.substr(1,i-1);
  56.             string right=str.substr(i+1,str.size()-i-2);
  57.             unionFind_.merge(left,right);
  58.         }
  59.         vector<string> ans;
  60.         int i=0;
  61.         for(const auto& v:unionFind_.size_){
  62.             if(v.second!=0 && i!=unionFind_.n_){
  63.                 string tmp=v.first+'('+to_string(v.second)+')';
  64.                 ans.emplace_back(tmp);
  65.                 i++;
  66.             }
  67.         }
  68.         return ans;
  69.     }
  70. };