题解 | 图上染色

import sys
from typing import List

def parse_input():
    n, m, q = map(int, sys.stdin.readline().strip().split())
    edges = [
        list(map(int, sys.stdin.readline().strip().split()))
        for _ in range(m)
    ]
    colors = [
        list(map(int, sys.stdin.readline().strip().split()))
        for _ in range(q)
    ]
    return n, edges, colors

class Solution:
    def __init__(self, n, edges) -> None:
        self.node_color: List[int] = [0] * n
        self.neighbors = self._build_neighbors(n, edges)
        self.max = 0

    def _build_neighbors(self, n, edges) -> List[List[int]]:
        neighbors = [[] for _ in range(n)]
        for u, v in edges:
            u, v = u - 1, v - 1
            neighbors[u].append(v)
            neighbors[v].append(u)
        return neighbors
    
    def resolve(self, turn_color) -> int:
        x, c = turn_color[0] - 1, turn_color[1]
        self.node_color[x] = c
        
        visited = set()
        def dfs(i) -> int:
            if self.node_color[i] != c:
                return 0
            visited.add(i)
            return 1 + sum(dfs(j) for j in self.neighbors[i] if j not in visited)

        candidate_max = dfs(x)
        self.max = max(self.max, candidate_max)
        return self.max

# Solution维护ans，在每次染色后更新
# 初始时每个节点只和自己连通
# 如何将连通的所有节点映射到一个值？先用dfs实现吧
# node_color: list, not_visited: set
# 根据edges和colors，构建每个节点和自己颜色相同的邻居节点
# 从每个节点出发，通过dfs统计连通节点数，更新ans

if __name__ == "__main__":
    n, edges, colors = parse_input()
    solution = Solution(n, edges)
    for color in colors:
        ans = solution.resolve(color)
        print(ans)