并查集

11 Oct 2023 in Algorithm Pageviews

并查集求祖宗节点!

将编号1~n的n个数经过多次合并到同一集合中，并判断指定的两个数是否有公共的祖先。

class Solution {
public:
    int find(int x)
    {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    void Merge()
    {
        int n = 0;
        int m = 0;
        cin >> n >> m;
        p.resize(n);
        std::generate(p.begin(), p.end(), [i = 0]() mutable {return i++;});
        while (m--) {
            int a = 0;
            int b = 0;
            string str;
            cin >> str >> a >> b;
            if (str == "Merge") {
                p[find(a)] = find(b);
            } else if (find(a) == find(b)) {
                cout << "In Same Node" << endl;
            } else {
                cout << "Not Same Node" << endl;
            }
        }
    }
    vector<int> p;
};

举例2：省份数量

有n个城市，其中一些彼此相连，另外一些没有相连，如果城市 a 与城市 b 直接相连，城市 b 与城市 c 直接相连，那么城市 a 和城市c 就间接相连。

省份是一组直接相连或间接相连的城市，组内不含其它没有相连的城市。

给你一个 n x n 的矩阵 IsConnected，其中 IsConnected[i][j] = 1 表示第 i 个城市与第 j 个城市直接相连，而 IsConnected[i][j] = 0 表示二者不相连。

返回矩阵中省份的数量。

示例1：

输入

IsConnected = [[1,1,0], [1,1,0], [0,0,1]];

输出

2

示例2：

输入

IsConnected = [[1,0,0], [0,1,0], [0,0,1]]

输出

3

代码实现如下

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> p;
    int find(int x)
    {
        if (p[x] != x) {
            p[x] = find(p[x]);
        }
        return p[x];
    }

    int FindCircleNum(vector<vector<int>> &M)
    {
        int n = M.size();
        p.resize(n);
        std::generate(p.begin(), p.end(), [i = 0]() mutable {return i++;});
        for (int i = 0; i < M.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (M[i][j] == 0) {
                    continue;
                }
                 
                if (find(i) != find(j)) {
                    p[find(i)] = find(j);
                    n--;
                }
            }
        }
        return n;
    }
};