并查集

并查集是一种维护集合的数据结构。它支持以下两个操作：

1.合并两个集合

2.判断两个元素是否在一个集合

初始化：一开始，每个元素都是一个独立的集合
查找：规定一个集合中只有一个根节点。查找操作就是反复寻找根节点，直至找到根节点。
合并：一般给出两个元素，要求把这两个元素所在集合合并。具体实现上先判断两个元素是否属于同一个集合，两个元素属于不同集合时才合并。(如给定元素A,B 合并操作Father[A]=B 或 Father[B]=A)

例题1

#include<bits/stdc++.h>
using namespace std;
#define N 100
int father[N];
bool isRoot[N] = {false};

// 寻找根节点 
int findfather(int x)
{
    int a = x;
    while(father[x]!=x)
    {
        x = father[x];
    }
    // 路径压缩 优化  可不写 
    while(a!=father[a])
    {
        int z = a;
        a = father[a];
        father[z]=x;
    }
    return x;
}
// 若两个元素不在一个集合中 则将它们合并 否则不操作 
void Union(int x,int y)
{
    int FatherX = findfather(x);
    int FatherY = findfather(y);
    if(FatherX!=FatherY)
        father[FatherX] = FatherY;
}
int main()
{
    //数码宝贝个数n  好朋友的组数m 
    int n,m;
    cin>>n>>m;
    int a,b;
    // 最开始每个元素都是一个独立的集合 
    for(int i=1;i<=n;++i)
    {
       father[i]=i;
    }
    // m组好友关系
    for(int j=0;j<m;++j)
    {
        cin>>a>>b;
        Union(a,b);
    }
    // 记录某节点是否为根节点 
    for(int i=1;i<=n;++i)
    {
        int f = findfather(i);
        isRoot[f]=true;
    }
    // 统计集合数量
    int count = 0;
    for(int i=1;i<=n;++i)
    {
        if(isRoot[i])
            count++;
    }
    cout<<count<<endl;
    return 0;    
} 

例题2 计算岛屿数量

思路：可DFS、BFS、并查集

//定义并查集类及其操作
class UnionFind{
    private:
// count计数最终的连通块数目
    int count;
    vector<int>father;
    public:
    UnionFind(vector<vector<char>>& v)
    {
        count = 0;
        father.clear();
        int row = v.size();
        int column = v[0].size();
        for(int i=0;i<row;++i)
        {
            for(int j=0;j<column;++j)
            {
                if(v[i][j]=='1')
                {
                //初始化每个符合要求的结点的父结点为其自身
                     father.push_back(i*column+j);
                     ++count;
                }
                else father.push_back(-1);
            }
        }
    }
    int find(int x)
    {
        while(father[x]!=x)
        {
            x = father[x];
        }
        return x;
    }
    void Union(int x,int y)
    {
        int father_x = find(x);
        int father_y = find(y);
        if(father_x!=father_y)
        {
            father[father_x]=father_y;
            --count;
        }

    }
    int getCount()
    {
        return count;
    }

};

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if(grid.empty()) return 0;
        UnionFind uf(grid);
        int r = grid.size();
        int c = grid[0].size();
        for(int i=0;i<r;++i)
        {
            for(int j=0;j<c;++j)
            {
                if(grid[i][j]=='1')
                {
                    int cur = i*c+j;
                    // 访问过即置0
                    grid[i][j] = '0';
                    //if(i-1>=0 && grid[i-1][j]=='1')
                    //    uf.Union(cur,(i-1)*c+j);
                    //if(j-1>=0 && grid[i][j-1]=='1')
                    //    uf.Union(cur,i*c+j-1);
                    // 向右向下搜索即可 左上已经搜索过 
                    // 注意这里的写法是连着的if
                    if(i+1<r && grid[i+1][j]=='1')
                        uf.Union(cur,(i+1)*c+j);
                    if(j+1<c && grid[i][j+1]=='1')
                        uf.Union(cur,i*c+j+1);

                }
            }
        }
        return uf.getCount();


    }
};