并查集

11 Oct 2023 in Algorithm Pageviews

并查集求祖宗节点!

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

class Solution {
public:
    Solution() {p.resize(10010);}

    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;
};