【AcWing16】【LeetCode】并查集Union Find-128/130/*1020-学完广度优先/深度优先要回来再看

推荐文章：

并查集图解及优化过程
并查集(Union-Find)算法介绍

学完广度优先/深度优先要回来再看
有另外的模板

模板

01最简单的

#include 
using namespace std;
const int N = 1000010;
int n, m;
int p[N];//父亲结点

//核心算法：
int find (int x) {
    if (p[x] != x) 	// 寻找p节点所在组的根节点，根节点具有性质id[root] = root，祖宗节点是个环
        p[x] = find(p[x]);//路径压缩--平摊开了
    return p[x];//返回祖宗结点
}

int main () {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n;i ++)
        p[i] = i;//编号
    
    while (m --) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'M')
            p[find(a)] = find(b);//把a加到b的集合中，让a的父节点变成b
        else {
            if (find(a) == find(b))//判断a和b的父亲结点是否相同
                puts("Yes");
            else
                puts("No");
        }
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

02维护size的并查集：

int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

03维护到祖宗节点距离的并查集(带权并查集)

 int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int root = find(p[x]);
            d[x] += d[p[x]];
            p[x] = root;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LeetCode 128. 最长连续序列

class Solution {
public:
    // cnt用于记录当前集合的元素个数
    unordered_map<int,int> uf, cnt;

    int find(int i){
        return i == uf[i] ? i: uf[i] = find(uf[i]);
    }

    int merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return cnt[x];
        uf[y] = x;
        //更新合并之后的连通分量的元素个数
        cnt[x] += cnt[y];
        return cnt[x];
    }

    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        
        for(int i: nums) 
        	uf[i] = i, cnt[i] = 1;
        	
        int ans = 1;
        
        for(int i: nums){
            if(i != INT_MAX && uf.count(i+1)) 
            	ans = max(ans, merge(i, i+1));
        }
        return ans;
    }
};

作者：jarvis1890
链接：https://leetcode.cn/problems/longest-consecutive-sequence/solution/ha-xi-biao-shi-xian-on-bing-cha-ji-liang-chong-shi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// 下面这个答案有解释，但是测试集只能部分通过–待研究

class Solution {
public:
    // rt 用于记录指向， sz 用于记录并查集这一子集的大小
    unordered_map<int, int> rt, sz;
    int find(int v){
        // 这一步写法综合了路径压缩以及根的查找
        return rt[v]==v?v:rt[v] = find(rt[v]); 
    }
    int merge(int u, int v){
        u = find(u); 
        v = find(v);
        // 如果u和v不在同一个集合中
        if (u != v){
            // 合并集合的size
            sz[u] += sz[v];
            // 修改元素的指向
            rt[v] = rt[u];
        }
        // merge 函数返回当前集合的大小
        return sz[u];
    }
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;
        int ans = 1;
        for (auto v:nums){
            // 对并查集进行初始化
            // rt[v] = v 代表v是自己所在这个集合的根
            rt[v] = v;
            sz[v] = 1;
        }
        for (auto v: nums){
            // 由于是连续数组，我们只需要考虑v与v-1就能照顾所有边
            if (rt.find(v-1) != rt.end())
                ans = max(ans, merge(v, -1));
        }
        return ans;
    }
};

作者：whiteAshes
链接：https://leetcode.cn/problems/longest-consecutive-sequence/solution/ti-mu-fen-xi-ji-yi-hua-sou-suo-bing-cha-ji-ji-lu-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

LeetCode 130. 被围绕的区域

class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if (board.empty()) return;
        int m = board.size(), n = board[0].size();
        ufSet(m * n + 1);
        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                if (board[row][col] == 'X') continue;
                if (!col || !row || row + 1 == m || col + 1 == n)
                    merge(m * n, row * n + col); // m * n 值，为集合头
                if (col > 0 && board[row][col - 1] == 'O')
                    merge(row * n + col - 1, row * n + col);
                if (row > 0 && board[row - 1][col] == 'O')
                    merge((row - 1) * n + col, row * n + col);
            }
        }
        for (int row = 0; row < m; ++row) {
            for (int col = 0; col < n; ++col) {
                // 通过 find 返回集合头来确实是否是第三种元素集
                if (board[row][col] == 'O' && find(row * n + col) != m * n)
                    board[row][col] = 'X';
            }
        }
    }

private:
    void ufSet(int n) {
        uf.resize(n);
        for (int i = 0; i < n; ++i)
            uf[i] = i;
    }

    int find(int p) {
        return uf[p] == p ? p : uf[p] = find(uf[p]);
    }

    void merge(int p, int q) {
        // 人为保持 uf.size()-1 为集合头
        int p1 = find(p), q2 = find(q);
        p1 == uf.size() - 1 ? uf[q2] = p1 : uf[p1] = q2;
    }

private:
    vector<int> uf;
};

作者：fengziL
链接：https://leetcode.cn/problems/surrounded-regions/solution/zhua-zhong-dian-san-chong-jie-fa-jian-ji-d621/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
public:
    void dfs(vector<vector<char>>& board,int n,int m,int x,int y)
    {
        if (x<0||y<0||x>=n||y>=m)
        return;
        if (board[x][y]=='O')
        {
            board[x][y]='X';
            dfs(board,n,m,x-1,y);
            dfs(board,n,m,x+1,y);
            dfs(board,n,m,x,y-1);
            dfs(board,n,m,x,y+1);
        }
    }
    void format(vector<vector<char>>& board,int n,int m,int x,int y)
    {
        if (x<0||y<0||x>=n||y>=m)
        return;
        if (board[x][y]=='O')
        {
            board[x][y]='A';
            format(board,n,m,x-1,y);
            format(board,n,m,x+1,y);
            format(board,n,m,x,y-1);
            format(board,n,m,x,y+1);
        }
    }
    void solve(vector<vector<char>>& board) {
      int n=board.size(),m=board[0].size();
      for (int i=0;i<m;i++)
        {
          format(board,n,m,0,i);
          format(board,n,m,n-1,i);
        }
      for (int i=1;i<n;i++)
        {
          format(board,n,m,i,0);
          format(board,n,m,i,m-1);
        }
      for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
          if (board[i][j]=='O')
            board[i][j]='X';
      for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
          if (board[i][j]=='A')
            board[i][j]='O';
    }
};

作者：whitejoce
链接：https://leetcode.cn/problems/surrounded-regions/solution/by-whitejoce-n54z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

LeetCode 1020. 飞地的数量