题解 | 图上染色

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> g(n + 1);
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> fa(n + 1, 0), sz(n + 1, 0);    // 仅对已染色点生效
    vector<long long> col(n + 1, 0);           // 0 表示未染色
    function<int(int)> find = [&](int x) {
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    };
    auto unite = [&](int a, int b, int& mx) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        fa[b] = a;
        sz[a] += sz[b];
        mx = max(mx, sz[a]);
    };

    int mx = 0;
    while (q--) {
        int u;
        long long c;
        cin >> u >> c;
        col[u] = c;
        fa[u] = u;
        sz[u] = 1;
        mx = max(mx, 1);  // 新建颜色块
        for (int v : g[u]) if (col[v] == c) unite(u, v, mx); // 仅与同色邻点合并
        cout << mx << '\n';
    }
    return 0;
}