Day 014-Q3 — 動的グラフの連結性（LCT + 橋の管理）

問題

N 頂点 0 辺のグラフに add/del/bridge クエリ。bridge は辺がブリッジ（削除で連結成分数が増加）かを判定。

制約

入出力例

4 7
add 1 2
add 2 3
bridge 1 3
add 1 3
bridge 1 3
del 1 3
bridge 1 3

No
No
Yes

ヒント (段階的開示)

模範解答 (Python)

📋 コピーimport sys
from sys import stdin

class LCTNode:
    def __init__(self):
        self.ch = [None, None]
        self.par = None
        self.rev = False
        self.val = 0
        self.min_val = 0
        self.lazy = 0

class LinkCutTree:
    def __init__(self, n):
        self.nodes = [LCTNode() for _ in range(n + 1)]
    def _is_root(self, v):
        p = v.par
        return p is None or (p.ch[0] is not v and p.ch[1] is not v)
    def _push_up(self, v):
        v.min_val = v.val
        for c in v.ch:
            if c:
                v.min_val = min(v.min_val, c.min_val)
    def _apply(self, v, add):
        v.val += add
        v.min_val += add
        v.lazy += add
    def _push_down(self, v):
        if v.rev:
            v.ch[0], v.ch[1] = v.ch[1], v.ch[0]
            for c in v.ch:
                if c:
                    c.rev ^= True
            v.rev = False
        if v.lazy:
            for c in v.ch:
                if c:
                    self._apply(c, v.lazy)
            v.lazy = 0
    def _rotate(self, v):
        p = v.par; g = p.par
        is_root_p = self._is_root(p)
        d = 1 if p.ch[0] is v else 0
        p.ch[1-d] = v.ch[d]
        if v.ch[d]:
            v.ch[d].par = p
        v.ch[d] = p
        p.par = v
        v.par = g
        if not is_root_p:
            if g.ch[0] is p:
                g.ch[0] = v
            else:
                g.ch[1] = v
        self._push_up(p)
        self._push_up(v)
    def _splay(self, v):
        stack = []
        x = v
        while not self._is_root(x):
            stack.append(x); x = x.par
        stack.append(x)
        for node in reversed(stack):
            self._push_down(node)
        while not self._is_root(v):
            p = v.par
            if not self._is_root(p):
                g = p.par
                if (g.ch[0] is p) == (p.ch[0] is v):
                    self._rotate(p)
                else:
                    self._rotate(v)
            self._rotate(v)
    def _access(self, v):
        last = None; cur = v
        while cur:
            self._splay(cur)
            cur.ch[1] = last
            self._push_up(cur)
            last = cur; cur = cur.par
        self._splay(v)
        return last
    def make_root(self, v):
        self._access(v); v.rev ^= True
    def link(self, u, v):
        self.make_root(u); u.par = v
    def cut(self, u, v):
        self.make_root(u); self._access(v)
        v.ch[0] = None
        if u.par is v:
            u.par = None
        self._push_up(v)
    def connected(self, u, v):
        self.make_root(u); self._access(v)
        return v.par is not None or v is u
    def path_min(self, u, v):
        self.make_root(u); self._access(v)
        return v.min_val
    def path_add(self, u, v, x):
        self.make_root(u); self._access(v)
        self._apply(v, x)


def solve():
    input_data = stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    lct = LinkCutTree(N)
    nodes = lct.nodes
    edge_count = {}
    out = []
    for _ in range(Q):
        op = input_data[idx]; idx += 1
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        if op == "add":
            key = (min(u,v), max(u,v))
            edge_count[key] = edge_count.get(key, 0) + 1
            if not lct.connected(nodes[u], nodes[v]):
                lct.link(nodes[u], nodes[v])
            else:
                lct.path_add(nodes[u], nodes[v], 1)
        elif op == "del":
            key = (min(u,v), max(u,v))
            edge_count[key] -= 1
            if edge_count[key] == 0:
                del edge_count[key]
            lct.path_add(nodes[u], nodes[v], -1)
        elif op == "bridge":
            if not lct.connected(nodes[u], nodes[v]):
                out.append("No")
            else:
                min_cnt = lct.path_min(nodes[u], nodes[v])
                out.append("Yes" if min_cnt == 0 else "No")
    print('\n'.join(out))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 完全オンライン動的 2-edge-connectivity

自己評価

自分の回答

気づき・メモ