Day 174-Q1 — 2026-10-10 | 一般グラフの無向頂点ジオグラフィ（花を縮める最大マッチング＋Gallai–Edmonds の D 集合）

📋 コピーimport sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n)]
    for i in range(m):
        u = int(data[2 + 2 * i]) - 1
        v = int(data[3 + 2 * i]) - 1
        adj[u].append(v)
        adj[v].append(u)

    match = [-1] * n
    base = list(range(n))
    p = [-1] * n
    used = [False] * n

    def lca(a, b):
        seen = [False] * n
        while True:
            a = base[a]
            seen[a] = True
            if match[a] == -1:
                break
            a = p[match[a]]
        while True:
            b = base[b]
            if seen[b]:
                return b
            b = p[match[b]]

    def mark_path(v, b, child, blossom):
        while base[v] != b:
            blossom[base[v]] = blossom[base[match[v]]] = True
            p[v] = child
            child = match[v]
            v = p[match[v]]

    def search(roots):
        # roots から交互木（森）を BFS で広げる。増加路が見つかればその端点を返す
        for i in range(n):
            used[i] = False
            p[i] = -1
            base[i] = i
        q = deque()
        for r in roots:
            used[r] = True
            q.append(r)
        while q:
            v = q.popleft()
            for to in adj[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if (to in roots_set and used[to]) or (match[to] != -1 and p[match[to]] != -1):
                    # 偶–偶の辺: 花を縮める
                    cb = lca(v, to)
                    blossom = [False] * n
                    mark_path(v, cb, to, blossom)
                    mark_path(to, cb, v, blossom)
                    for i in range(n):
                        if blossom[base[i]]:
                            base[i] = cb
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif p[to] == -1:
                    p[to] = v
                    if match[to] == -1:
                        return to
                    nxt = match[to]
                    used[nxt] = True
                    q.append(nxt)
        return -1

    # 貪欲な初期マッチング
    for v in range(n):
        if match[v] == -1:
            for to in adj[v]:
                if match[to] == -1:
                    match[v] = to
                    match[to] = v
                    break
    for r in range(n):
        if match[r] == -1:
            roots_set = {r}
            t = search([r])
            while t != -1:
                pv = p[t]
                ppv = match[pv]
                match[t] = pv
                match[pv] = t
                t = ppv
    # Gallai–Edmonds: 露出頂点すべてを根にした最後の探索で「偶」になる頂点が D
    roots = [v for v in range(n) if match[v] == -1]
    roots_set = set(roots)
    t = search(roots)
    assert t == -1
    print(''.join('L' if used[v] else 'W' for v in range(n)))


main()