Day 127-Q2 | MSTの辺分類

問題

$N$ 頂点 $M$ 辺の連結無向グラフが与えられる（多重辺・自己ループなし）。各辺 $i$ には重み $w_i$ がある。各辺を次の3種類に分類せよ。

A（Always）: すべてのMSTに含まれる辺
S（Sometimes）: あるMSTには含まれるが含まれないMSTもある辺
N（Never）: どのMSTにも含まれない辺

入力形式

N M
u_1 v_1 w_1
...
u_M v_M w_M

制約

$2 \le N \le 2000$

$N-1 \le M \le \min(7500, N(N-1)/2)$

$1 \le w_i \le 10^9$

グラフは連結

入出力例

入力例1

出力例1

S
S
S
S
N

重み1の4辺は正方形。3本選べばMST(合計3)。対角線(重み2)はどのMSTにも入らない。

概念図

ヒント（段階的開示）

ヒント1（方向性）

各辺を仮に除いたり強制採用したりしてMSTを再計算すると $O(M\cdot M\log N)$ になり間に合わない。重みでグループ化して一括処理する方法を考える。

ヒント2（アプローチ）

重み $w$ 未満の辺だけで作る連結成分の分割はどのMSTでも共通。重み $w$ のグループの各辺で、処理前に既に同成分なら「N」。候補辺だけで作る縮約グラフ上で橋なら「A」、サイクル上なら「S」。

ヒント3（誘導）

橋検出は多重辺対応のため親「辺ID」で戻りを除外する。

def find_bridges(num_local, adj):  # adj[v]=[(to, edge_id), ...]
    order=[-1]*num_local; low=[0]*num_local; bridges=set(); timer=0
    for start in range(num_local):
        if order[start] != -1: continue
        stack=[(start,-1,iter(adj[start]))]
        order[start]=low[start]=timer; timer+=1
        while stack:
            v,pe,it=stack[-1]; advanced=False
            for to,eid in it:
                if eid==pe: continue
                if order[to]==-1:
                    order[to]=low[to]=timer; timer+=1
                    stack.append((to,eid,iter(adj[to]))); advanced=True; break
                else:
                    low[v]=min(low[v],order[to])
            if not advanced:
                stack.pop()
                if stack:
                    pv=stack[-1][0]; low[pv]=min(low[pv],low[v])
                    if low[v]>order[pv]: bridges.add(pe)
    return bridges

模範解答 (Python)

import sys


def solve():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(input_data[idx]); idx += 1
    m = int(input_data[idx]); idx += 1

    edges = []
    for i in range(m):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        w = int(input_data[idx]); idx += 1
        edges.append((w, u, v, i))

    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(x, y):
        x, y = find(x), find(y)
        if x == y:
            return False
        parent[x] = y
        return True

    result = [''] * m
    edges.sort(key=lambda e: e[0])

    i = 0
    while i < m:
        j = i
        w = edges[i][0]
        while j < m and edges[j][0] == w:
            j += 1
        group = edges[i:j]

        candidates = []
        for (_, u, v, eidx) in group:
            ru, rv = find(u), find(v)
            if ru == rv:
                result[eidx] = 'N'
            else:
                candidates.append((ru, rv, eidx))

        if candidates:
            comp_ids = {}
            for ru, rv, _ in candidates:
                if ru not in comp_ids:
                    comp_ids[ru] = len(comp_ids)
                if rv not in comp_ids:
                    comp_ids[rv] = len(comp_ids)
            num_local = len(comp_ids)
            adj = [[] for _ in range(num_local)]
            for local_eid, (ru, rv, eidx) in enumerate(candidates):
                lu, lv = comp_ids[ru], comp_ids[rv]
                adj[lu].append((lv, local_eid))
                adj[lv].append((lu, local_eid))

            order_arr = [-1] * num_local
            low = [0] * num_local
            bridges = set()
            timer = 0
            for start in range(num_local):
                if order_arr[start] != -1:
                    continue
                stack = [(start, -1, iter(adj[start]))]
                order_arr[start] = low[start] = timer; timer += 1
                while stack:
                    v, pe, it = stack[-1]
                    advanced = False
                    for to, eid in it:
                        if eid == pe:
                            continue
                        if order_arr[to] == -1:
                            order_arr[to] = low[to] = timer; timer += 1
                            stack.append((to, eid, iter(adj[to])))
                            advanced = True
                            break
                        else:
                            low[v] = min(low[v], order_arr[to])
                    if not advanced:
                        stack.pop()
                        if stack:
                            pv = stack[-1][0]
                            low[pv] = min(low[pv], low[v])
                            if low[v] > order_arr[pv]:
                                bridges.add(pe)

            for local_eid, (ru, rv, eidx) in enumerate(candidates):
                result[eidx] = 'A' if local_eid in bridges else 'S'
                union(ru, rv)

        i = j

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


solve()

Step-by-Step 解説

1重みでグループ化する理由
重み$w$未満の辺集合が作る連結成分の分割は交換補題によりどのMSTでも共通なので、重みごとに一括処理してよい。

2never判定
グループ処理直前に既に同成分の辺はどう選んでも閉路を作るので絶対に「N」。

3橋検出
候補辺の縮約グラフで橋は必ず使う辺(「A」)、サイクル上の辺は代替可能(「S」)。

4多重辺対応
親「頂点」だけでなく親「辺ID」で戻りを除外しないと多重辺で誤判定する。

5次グループへの反映
判定完了後にA・S両方をまとめてDSUに反映してから次の重みグループへ進む。

よくあるミス

ミス	原因	正しい書き方
橋検出で親「頂点」だけ除外	多重辺で誤って橋と誤認	親「辺ID」を記録して除外する
never判定をグループ処理後に行う	処理前の状態を確認していない	グループ処理を始める前のfind結果で判定
候補辺の反映を判定と同時に行う	反映順で結果がぶれる	判定を全て終えてからまとめて反映
再帰でTarjanを実装しスタックオーバーフロー	縮約グラフが直鎖状になりうる	明示的スタックの反復実装にする

次のステップ

発展: 辺重みの微小変化に対するMST合計重みの変化をこの分類で $O(1)$ 判定
次回予告: 区間最頻値クエリ（Range Mode Query・平方分割によるオフライン処理）

自己評価

完全理解おおむね理解要復習

Day 127-Q2 — MSTの辺分類（Must-use / May-use / Never-use）

問題