并查集

使用 UnionFind uf(n);

```cpp
struct UnionFind {
int n;
vector parent, size;

UnionFind(int n) {
this->n = n;
parent = vector<int>(n);
size = vector<int>(n, 1);
for (int i = 0; i < n; ++i)
    parent[i] = i;
}

int find(int idx) {
    if (parent[idx] == idx)
        return idx;
    return parent[idx] = find(parent[idx]);
}

void connect(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa != fb) {
        if (size[fa] > size[fb]) {
            parent[fb] = fa;
            size[fa] += size[fb];
        } else {
            parent[fa] = fb;
            size[fb] += size[fa];
        }
    }
}

unordered_map<int, vector<int>> components() {
    unordered_map<int, vector<int>> res;
    for (int i = 0; i < n; ++i)
        res[find(i)].emplace_back(i);
    return res;
}

};
```

---

最后更新: 2022-11-15

评论