题解 | #图上染色#

题目链接

图上染色

题目描述

给定一个 $n$ 个节点 $m$ 条边的无向图。初始时，所有节点都没有颜色。现有 $q$ 次操作，每次操作会选择一个未染色的节点，并将其染成颜色 $c$ 。要求在每次操作之后，都输出当前所有单色连通块大小的最大值。

一个单色连通块指的是一个节点集合，其中所有节点颜色相同，且集合内任意两点都存在一条只经过该集合内其他节点的路径。

解题思路

这是一个动态维护图连通性的问题，且连通性与颜色相关。每次染色操作都会改变图的状态，我们需要高效地回答随后的查询。

核心思想：为每种颜色维护一个并查集

为什么选择并查集 (DSU)?

并查集是解决动态连通性问题的最佳工具。它能高效地处理“合并”两个集合以及“查询”某个元素属于哪个集合的操作。
如何处理多种颜色?

由于连通性是基于颜色的（只有相同颜色的节点才能在同一个连通块内），一个全局的并查集无法胜任。因此，我们为每一种颜色都维护一个独立的并查集。
- 我们可以使用一个 map 来存储这些并查集，其中 key 是颜色，value 是该颜色对应的并查集实例。例如：map<int, DSU> dsu_by_color。
如何优化空间?

如果每个并查集都使用大小为 $N$ 的数组，当颜色种类很多时，内存开销会非常大。为了优化空间，我们的并查集内部不使用数组，而是使用 map 来存储节点的父节点和集合大小。这样，一个并查集占用的空间只与被染上该颜色的节点数量成正比。
如何追踪全局最大值?

我们需要快速找到所有颜色、所有连通块中的最大尺寸。这可以通过一个 multiset 来实现。
- 我们额外用一个 map<int, int> max_size_per_color 来记录每种颜色的最大连通块尺寸。
- 然后，我们将这个 map 中的所有值（即每种颜色的最大块尺寸）存入一个 multiset。multiset 会自动排序，我们随时可以通过取其最后一个元素 (*rbegin()) 得到全局最大值。

算法流程

对于每一次“将节点 $u$ 染成颜色 $c$ ”的操作：

更新节点 $u$ 的颜色记录。
获取颜色 $c$ 对应的并查集 dsu_c (如果不存在则新建)。
记录操作前颜色 $c$ 的最大连通块尺寸 old_max_c。
在 dsu_c 中，将节点 $u$ 初始化为一个大小为 1 的新集合。
遍历 $u$ 的所有邻居 $v$ ：
- 如果 $v$ 的颜色也是 $c$ ，就在 dsu_c 中合并 $u$ 和 $v$ 所在的集合。
合并结束后， $u$ 所在的新连通块大小为 dsu_c.size(u)。
颜色 $c$ 的新最大连通块尺寸 new_max_c 就是 max(old_max_c, dsu_c.size(u))。
更新全局 multiset：先移除 old_max_c (如果它>0)，再插入 new_max_c。
本次操作的答案就是 multiset 中的最大元素。

这个方法将每次更新的复杂度控制在与被染色节点的度数相关的对数级别，能够高效地处理所有操作和查询。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <numeric>
#include <algorithm>

using namespace std;

struct DSU {
    map<int, int> parent;
    map<int, int> sz;

    void make_set(int v) {
        if (parent.find(v) == parent.end()) {
            parent[v] = v;
            sz[v] = 1;
        }
    }

    int find_set(int v) {
        if (parent.find(v) == parent.end()) {
            make_set(v);
            return v;
        }
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void unite_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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> colors(n + 1, 0);
    map<int, DSU> dsu_by_color;
    map<int, int> max_size_per_color;
    multiset<int> all_max_sizes;

    for (int k = 0; k < q; ++k) {
        int u, c;
        cin >> u >> c;

        colors[u] = c;

        DSU& dsu_c = dsu_by_color[c];
        dsu_c.make_set(u);

        int old_max_c = max_size_per_color.count(c) ? max_size_per_color[c] : 0;

        for (int v : adj[u]) {
            if (colors[v] == c) {
                dsu_c.unite_sets(u, v);
            }
        }

        int new_comp_size = dsu_c.sz[dsu_c.find_set(u)];
        int new_max_c = max(old_max_c, new_comp_size);
        
        if (old_max_c != new_max_c) {
            if (old_max_c > 0) {
                all_max_sizes.erase(all_max_sizes.find(old_max_c));
            }
            all_max_sizes.insert(new_max_c);
            max_size_per_color[c] = new_max_c;
        }

        if (all_max_sizes.empty()) {
             // This case handles the very first coloring
            if (new_max_c > 0) {
                 all_max_sizes.insert(new_max_c);
                 max_size_per_color[c] = new_max_c;
            }
        }
        
        if (all_max_sizes.empty()) {
            cout << 0 << "\n";
        } else {
            cout << *all_max_sizes.rbegin() << "\n";
        }
    }

    return 0;
}

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

public class Main {
    static class DSU {
        Map<Integer, Integer> parent = new HashMap<>();
        Map<Integer, Integer> sz = new HashMap<>();

        public void makeSet(int v) {
            if (!parent.containsKey(v)) {
                parent.put(v, v);
                sz.put(v, 1);
            }
        }

        public int findSet(int v) {
            if (!parent.containsKey(v)) {
                makeSet(v);
                return v;
            }
            if (v == parent.get(v)) {
                return v;
            }
            int root = findSet(parent.get(v));
            parent.put(v, root);
            return root;
        }

        public void uniteSets(int a, int b) {
            a = findSet(a);
            b = findSet(b);
            if (a != b) {
                if (sz.get(a) < sz.get(b)) {
                    int temp = a; a = b; b = temp;
                }
                parent.put(b, a);
                sz.put(a, sz.get(a) + sz.get(b));
            }
        }
    }
    
    // Using TreeMap as a multiset substitute
    static void multisetRemove(TreeMap<Integer, Integer> ms, int val) {
        ms.put(val, ms.get(val) - 1);
        if (ms.get(val) == 0) {
            ms.remove(val);
        }
    }
    
    static void multisetAdd(TreeMap<Integer, Integer> ms, int val) {
        ms.put(val, ms.getOrDefault(val, 0) + 1);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        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);
        }

        int[] colors = new int[n + 1];
        Map<Integer, DSU> dsuByColor = new HashMap<>();
        Map<Integer, Integer> maxSizePerColor = new HashMap<>();
        TreeMap<Integer, Integer> allMaxSizes = new TreeMap<>(); // Simulating multiset

        for (int k = 0; k < q; k++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            colors[u] = c;
            
            dsuByColor.putIfAbsent(c, new DSU());
            DSU dsuC = dsuByColor.get(c);
            dsuC.makeSet(u);

            int oldMaxC = maxSizePerColor.getOrDefault(c, 0);

            for (int v : adj.get(u)) {
                if (colors[v] == c) {
                    dsuC.uniteSets(u, v);
                }
            }
            
            int newCompSize = dsuC.sz.get(dsuC.findSet(u));
            int newMaxC = Math.max(oldMaxC, newCompSize);

            if (oldMaxC != newMaxC) {
                if (oldMaxC > 0) {
                    multisetRemove(allMaxSizes, oldMaxC);
                }
                multisetAdd(allMaxSizes, newMaxC);
                maxSizePerColor.put(c, newMaxC);
            }
            
            if (allMaxSizes.isEmpty()) {
                if (newMaxC > 0) {
                    multisetAdd(allMaxSizes, newMaxC);
                    maxSizePerColor.put(c, newMaxC);
                }
            }
            
            if (allMaxSizes.isEmpty()) {
                System.out.println(0);
            } else {
                System.out.println(allMaxSizes.lastKey());
            }
        }
    }
}

import sys

# It's recommended to increase recursion limit for DSU in Python
sys.setrecursionlimit(200005) 

class DSU:
    def __init__(self):
        self.parent = {}
        self.sz = {}

    def find(self, i):
        if i not in self.parent:
            self.parent[i] = i
            self.sz[i] = 1
        
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            if self.sz[root_i] < self.sz[root_j]:
                root_i, root_j = root_j, root_i
            self.parent[root_j] = root_i
            self.sz[root_i] += self.sz[root_j]

def main():
    try:
        input = sys.stdin.readline
        n, m, q = map(int, input().split())
        
        adj = [[] for _ in range(n + 1)]
        for _ in range(m):
            u, v = map(int, input().split())
            adj[u].append(v)
            adj[v].append(u)
            
        colors = [0] * (n + 1)
        dsu_by_color = {}
        max_size_per_color = {}
        
        # In Python, a list can be kept sorted to simulate a multiset,
        # but it's inefficient. A better approach for performance would
        # be a balanced binary search tree library, but for simplicity
        # let's just find the max of values each time.
        
        for _ in range(q):
            u, c = map(int, input().split())
            colors[u] = c
            
            if c not in dsu_by_color:
                dsu_by_color[c] = DSU()
            
            dsu_c = dsu_by_color[c]
            # The find method implicitly creates the set if it doesn't exist.
            dsu_c.find(u)
            
            old_max_c = max_size_per_color.get(c, 0)
            
            for v in adj[u]:
                if colors[v] == c:
                    dsu_c.union(u, v)
            
            root_u = dsu_c.find(u)
            new_comp_size = dsu_c.sz[root_u]
            new_max_c = max(old_max_c, new_comp_size)
            max_size_per_color[c] = new_max_c
            
            if not max_size_per_color:
                print(0)
            else:
                print(max(max_size_per_color.values()))

    except (IOError, ValueError):
        pass

if __name__ == "__main__":
    main()

算法及复杂度

算法: 并查集 (Disjoint Set Union)
时间复杂度:
- 并查集内部使用 map 实现，单次 find 或 unite 操作的平均时间复杂度为 $\mathcal{O}(\alpha(N)\log N)$ ，其中 $\alpha$ 是反阿克曼函数，可以看作是一个极小的常数。
- 在所有 $q$ 次查询中，每条边最多只会在其两个端点被染上同一种颜色时，才触发一次 unite 检查。因此，所有并查集操作的总时间为 $\mathcal{O}(M \log N)$ 。
- 每次查询中，对 multiset (或等价结构) 的操作需要 $\mathcal{O}(\log Q)$ 时间。
- 因此，总的时间复杂度为 $\mathcal{O}(M \log N + Q \log Q)$ 。
空间复杂度: 邻接表需要 $\mathcal{O}(N+M)$ 的空间。并查集和各个 map 的总空间与染色的节点数和颜色数相关，最坏情况下为 $\mathcal{O}(N+M+Q)$ 。