(旧存档) 牛客多校第三场-G题

G 数据结构

题意

给你一个图，刚开始有 $n$ 个点，每个点 $i$ 在第 $i$ 组。有 $q$ 个操作，每次操作将组 $i$ 邻接的所有顶点 $v$ 所在的组 $g$ 合并到一个组 (合并后，被合并的组为空)，问最后每个点属于哪个组。

思路

关键点在于，如何合并一个组：

1. 快速合并顶点：使用并查集即可
2. 快速合并顶点关系（边）：当两个组合并时，将组 $i$ 的出边和组 $j$ 的出边合并即可，先清空组内的出边。由于合并后，被合并的组为空，因此清空被合并的组的出边。

在合并边集时：

1. 如果使用 vector, 应使用启发式合并（小的合并到大的边集中），从而尽量减少合并的次数。
2. 如果使用 list, 直接使用 splice 进行 $O(1)$ 合并
3. 手写链表避免了内存分配，比上述 std 容器更快

关键

合并点集与合并点不同，需要额外维护边集

代码1

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 8e5 + 5;
int fa[N];
vector<int> g[N];

void init(int n) {
    for (int i = 0; i < n; ++i) {
        g[i].clear();
        fa[i] = i;
    }
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t, n, m, x, y, q, o;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init(n);
        for (int i = 0; i < m; ++i) {
            cin >> x >> y;
            g[x].emplace_back(y);
            g[y].emplace_back(x);
        }
        cin >> q;
        for (int i = 0; i < q; ++i) {
            cin >> o;
            if (find(o) != o) continue;

            auto temp = g[o];
            g[o].clear();

            for (int u: temp) {
                u = find(u);
                if (u == o) continue;

                fa[u] = o;

                if (g[o].size() < g[u].size()) g[o].swap(g[u]);
                copy_if(g[u].begin(), g[u].end(), back_inserter(g[o]), [o](const int& x) {return find(x) != o;});
                g[u].clear();
            }
        }

        for (int i = 0; i < n; ++i) {
            cout << find(i) << " \n"[i == n - 1];
        }
    }
    return 0;
}

代码2

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 8e5 + 5;
int fa[N];
list<int> g[N];

void init(int n) {
    for (int i = 0; i < n; ++i) {
        g[i].clear();
        fa[i] = i;
    }
}

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int t, n, m, x, y, q, o;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init(n);
        for (int i = 0; i < m; ++i) {
            cin >> x >> y;
            g[x].emplace_back(y);
            g[y].emplace_back(x);
        }
        cin >> q;
        for (int i = 0; i < q; ++i) {
            cin >> o;
            if (find(o) != o) continue;

            auto temp = list<int>();
            for (int u: g[o]) {
                u = find(u);
                if (u == o) continue;
                fa[u] = o;
                temp.splice(temp.end(), g[u]);
            }
            g[o] = move(temp);
        }

        for (int i = 0; i < n; ++i) 
            cout << find(i) << " \n"[i == n - 1];
    }
    return 0;
}