Day 081-Q3 — 動的グラフ辺着色（Undo DSU + 二部グラフ性の動的判定）

問題

$N$ 頂点の無向グラフに対し，$Q$ 個のクエリを処理せよ：

• A $u$ $v$: 辺 $(u, v)$ を追加
• R $u$ $v$: 辺 $(u, v)$ を削除
• Q $u$ $v$: $u$-$v$ の連結性と，連結成分の二部グラフ判定を答える

答えは NO（非連結），YES 二部（連結かつ二部グラフ），YES 非二部（連結かつ奇数閉路あり）のいずれか。

入出力例

4 8
A 1 2
A 2 3
A 3 4
Q 1 4
A 4 1
Q 1 3
R 4 1
Q 1 4

YES 二部
YES 非二部
YES 二部

概念図: パリティ DSU と二部グラフ判定

ヒント

class UndoDSU:
    def find(self, x):
        """パス圧縮なし (Undo のため)"""
        p = 0
        while self.par[x] != x:
            p ^= self.parity[x]
            x = self.par[x]
        return x, p

    def union(self, u, v):
        ru, pu = self.find(u)
        rv, pv = self.find(v)
        if ru == rv:
            if pu == pv:  # 同パリティ → 奇数閉路
                self.bipartite[ru] = False
            return
        # rank による union (高い方が根)
        # parity[rv] = pu ^ pv ^ 1 に設定

    def undo(self):
        # history から最後の union を逆順に復元

模範解答（Union-Find + パリティ版 / 辺追加のみ）

import sys
def solve():
    input = sys.stdin.readline
    N, Q = map(int, input().split())

    parent = list(range(N+1))
    rank = [0] * (N+1)
    parity = [0] * (N+1)  # 根への距離 mod 2
    bipartite = [True] * (N+1)

    def find(x):
        if parent[x] == x: return x, 0
        root, p = find(parent[x])
        parity[x] ^= parity[parent[x]]
        parent[x] = root
        return root, parity[x]

    def union(x, y):
        rx, px = find(x); ry, py = find(y)
        if rx == ry:
            if px == py: bipartite[rx] = False
            return
        if rank[rx] < rank[ry]: rx, ry = ry, rx; px, py = py, px
        parent[ry] = rx
        parity[ry] = px ^ py ^ 1
        bipartite[rx] = bipartite[rx] and bipartite[ry]
        if rank[rx] == rank[ry]: rank[rx] += 1

    edges = set()
    out = []
    for _ in range(Q):
        line = input().split()
        t, u, v = line[0], int(line[1]), int(line[2])
        if t == 'A':
            if (u, v) not in edges and (v, u) not in edges:
                edges.add((u, v)); union(u, v)
        elif t == 'R':
            edges.discard((u, v)); edges.discard((v, u))
        else:
            ru, _ = find(u); rv, _ = find(v)
            if ru != rv: out.append("NO")
            elif bipartite[find(u)[0]]: out.append("YES 二部")
            else: out.append("YES 非二部")

    print('\n'.join(out))

solve()

Step-by-Step 解説

Step 1: パリティ DSU の設計

各ノードに「根への距離 mod 2」を持たせる。パス圧縮時: parity[x] ^= parity[parent[x]]。union 時: parity[ry] = pu ^ pv ^ 1（辺で距離差 1）。

Step 2: 奇数閉路の検出

同一成分内で辺 $(u, v)$ を追加するとき，$\text{parity}[u] == \text{parity}[v]$（同じ側）なら奇数閉路 → 成分を非二部グラフとしてマーク。

Step 3: 辺削除の対応（Undo DSU）

パス圧縮を禁止し，rank による union のみ使用（$O(\log N)$ per op）。各 union を history に記録，undo 時に逆順で復元。

Step 4: Offline Divide & Conquer

各辺の生存区間 [t_add, t_remove) を記録 → 時刻軸のセグメント木に登録 → solve(node, lo, hi) で DFS: ノードの辺を union → 子を再帰 → undo。全体 $O((N+Q) \log Q \cdot \log N)$。

よくあるミス

次のステップ

• 発展問題: Offline Dynamic 2-Coloring（辺追加・削除 + パリティクエリの完全 Offline 版）
• Link-Cut Tree に parity を持たせた完全 Online 実装

自己評価