图上染色

[题目链接](https://www.nowcoder.com/practice/93feea118678417db803ea62301ed3b1)

思路

给定一个 个节点、 条边的无向图，初始所有节点无颜色。每次操作将一个未着色节点染为某种颜色，操作后询问所有颜色相同的连通块中，最大块的大小。

关键观察

"颜色相同的连通块"是指：在原图中，若干节点两两相邻，且它们的颜色完全相同，形成的极大子图。

当我们给节点 染色 之后，只需检查 的邻居中是否也有颜色为 的节点，若有则将它们合并到同一个连通块（用并查集实现）。

算法设计

使用带权并查集（Union-Find / DSU）维护同色连通块大小：

  1. 初始化并查集，每个节点为独立集合，大小为 1。
  2. 维护每个节点的颜色数组 color[]，初始为 0（未着色）。
  3. 维护全局答案 ans。
  4. 对每次操作 (node, c)：

- 设置 color[node] = c

- 遍历 node 的所有邻居 nb：若 color[nb] == c，则合并 node 与 nb 所在集合

- 更新 ans = max(ans, getSize(node))

- 输出 ans

正确性

由于每个节点只会被染色一次，且染色后颜色不变，合并操作是单向增量的，不会出现需要"分裂"集合的情况，因此并查集完全适用。

全局答案是单调不减的（每次操作只会新增或合并块，不会减小），因此只需维护历史最大值。

样例演示（示例1）

图结构：1-2, 2-3, 3-4, 3-5, 1-5

操作序列：

操作 着色 动作 最大块
1 节点1染色1 邻居2,5未着色，无合并 1
2 节点2染色3 邻居1(色1≠3)，无合并 1
3 节点4染色1 邻居3未着色，无合并 1
4 节点3染色1 邻居4(色1=1)合并，块大小=2 2
5 节点5染色1 邻居1(色1=1)合并，邻居3(色1=1)合并，块大小=4 4

代码

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

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) x = parent[x] = parent[parent[x]];
        return x;
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
    int getSize(int x) { return sz[find(x)]; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

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

    vector<int> color(n + 1, 0);
    DSU dsu(n + 1);
    int ans = 0;

    for (int i = 0; i < q; i++) {
        int node, c;
        cin >> node >> c;
        color[node] = c;

        for (int nb : adj[node]) {
            if (color[nb] == c) {
                dsu.unite(node, nb);
            }
        }
        ans = max(ans, dsu.getSize(node));
        cout << ans << '\n';
    }

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] parent, sz;

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

    static void unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (sz[a] < sz[b]) { int t = a; a = b; b = t; }
        parent[b] = a;
        sz[a] += sz[b];
    }

    static int getSize(int x) { return sz[find(x)]; }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            adj.get(u).add(v);
            adj.get(v).add(u);
        }

        parent = new int[n + 1];
        sz = new int[n + 1];
        for (int i = 0; i <= n; i++) { parent[i] = i; sz[i] = 1; }

        int[] color = new int[n + 1];
        int ans = 0;

        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            color[node] = c;

            for (int nb : adj.get(node)) {
                if (color[nb] == c) {
                    unite(node, nb);
                }
            }
            ans = Math.max(ans, getSize(node));
            sb.append(ans).append('\n');
        }

        System.out.print(sb);
    }
}

复杂度分析

  • 时间复杂度：，其中 为节点的平均度数， 为反阿克曼函数（近似常数）。每次操作只遍历当前节点的邻居，并查集操作均摊 。
  • 空间复杂度：。存储邻接表和并查集数组。