323. Number of Connected Components in an Undirected Graph

union-find O(n) time O(n) space

class Solution {
public:
    int countComponents(int n, vector<pair<int, int>>& edges) {
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        res = n;
        for (const auto &e : edges) {
            merge(e.first, e.second);
        }
        return res;
    }

    int find(int x) {
        while (x != parent[x]) {
            x = parent[x] = parent[parent[x]];
        }
        return x;
    }

    void merge(int x, int y) {
        int px = find(x);
        int py = find(y);
        if (px != py) {
            parent[px] = py;
            --res;
        }
    }

    vector<int> parent;
    int res;
};