C#和.Net框架

参考文章:算法学习笔记(1) : 并查集
参考文章:分享｜（建议收藏）LeetCoder 并查集模板

什么是并查集

• 并查集有两个操作,合并和查询,用一个元素代表与其关联的一类元素,可以有效解决集合或者图中的连通性问题.

初始化操作

• 初始化操作让每个元素的自己单独为一个集合,但实际应用的时候应根据题意初始化并查集.

//最基础的并查集初始化
int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

查询操作

• 查询操作用于查询某一个元素属于哪一个集合,这个集合由一个元素代表,返回这个代表元素

  inline int find(x)
  {
    if(fa[x] != x)
        return find(fa[x]);
    else
        return x;
  }
  

合并操作

• 合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。

  inline void merge(int x,int y)
  {
    int findx = find(x);
    int findy = find(y);
    fx[findy] = findy;
  }
  

优化1:路径压缩

• 路径压缩用于解决并查集合并过程中可能导致深度过高,造成查询效率下降的问题.
• 路径压缩就说:要我们在查询的过程中，把沿途的每个节点的父节点都设为根节点即可。下一次再查询时，我们就可以省很多事。这用递归的写法很容易实现：

inline int find(int x)
{
    if(find(x) == x)
        return x;
    else
    {
        fa[x] = find(fa[x]);
        return fa[x];
    }
}

//极简写法
inline int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}

优化2:按秩合并

• 路径压缩优化后，并查集并非都是一个菊花图（只有两层的树的俗称）
  • 只有在路径压缩时才会优化某一条路径,所以某一时刻的并查集可能比较复杂
• 对于复杂的两个并查集合并,更好的做法是将深度低的并查集合并到深度深的并查集上,这样不会造成合并后并查集深度增加.
  • 因此对每一个并查集用rank表示其深度,在合并是根据rank值进行合并
  • 注意如果深度相同并且不是同一个并查集,进行合并后rank会+1

inline void merge(int x,int y)
{
    int findx = find(x);
    int findy = find(y);
    if(rank[x] > rank[y])
        fa[findy] = findx;
    else
        fa[findx] = findy;

    if(rank[findx] == rank[findy] && findx != findy)
        rank[findy]++; 
}

模板

//模板
//https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
class UnionFind{
private:
    vector<int> fa;
    vector<int> rank;
    int count;
public:
    UnionFind(){}
    UnionFind(vector<vector<char>>& grid)//Init
    {
        count = 0;
        int m = grid.size();
        int n = grid[0].size();
        fa.resize(n*m,0);
        rank.resize(n*m,0);
        for(int i = 0; i < grid.size();++i)
        {
            for(int j = 0; j < grid[0].size();++j)
            {
                if(grid[i][j] == '1')
                {
                    fa[i*n+j] = i*n+j;
                    ++count;
                }
                else
                    fa[i*n+j] = -1;
                rank[i*n+j] = 1;
            }
        }
    }

    inline int find(int x)
    {
        return x == fa[x]? x : (fa[x] = find(fa[x]));
    }

    inline void merge(int x,int y)
    {
        int fx = find(x);
        int fy = find(y);
        if(rank[fx] > rank[fy])
            fa[fy] = fx;
        else
            fa[fx] = fy;
        if(rank[fx] == rank[fy] && fx != fy)
            rank[fy]++;
        if(fx != fy)
            --count;
    }

    inline int getCount()
    {
        return count;
    }
};