AIで解説 AtCoder攻略　MST・SCC・フロー

MST・SCC・フローページの位置づけ

項目	内容
必修度	発展
学習目安	発展
前提	グラフ・優先度付きキュー
対象問題	56問（推定値あり56問、未算出0問）

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

学習目安	difficulty推定値	問題数
入門	difficulty < 0	2
標準	0〜799	14
標準〜発展	800〜1199	9
発展	1200以上	31
未算出	—	0

探索だけでは扱えないグラフの構造を、MST・トポロジカルソート・SCC・二部マッチング・最大流へ分解します。どの道具も「何を最適化・判定しているか」を先に固定します。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

MST・SCC・フローの見分け方

辺の重みを選びながら全頂点をつなぐ
依存関係の順序や強連結成分を求める
容量・マッチング・カットで制約を表せる

MST・SCC・フローの実装前チェック

グラフを無向・有向、重み付き・容量付きに分ける
MSTと最短路を混同しない
フローの頂点・辺の向きと残余グラフを確認する

先に確認する文法・ライブラリ

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

代表問題で実装を確認する

最初の一問として、ABC218 E H. Destruction（公式解説）を解きます。辺を重みの小さい順に調べ、Kruskal法で残す辺を決めます。閉路になる正の重みの辺だけを壊すと、その費用の合計が最小になります。

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
edges.sort(key=lambda edge: edge[2])

parent = list(range(N))
size = [1] * N

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

answer = 0
for a, b, cost in edges:
    a -= 1
    b -= 1
    ra, rb = find(a), find(b)
    if ra == rb:
        if cost > 0:
            answer += cost
    else:
        if size[ra] < size[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]

print(answer)

辺をソートするためO(M log M)、Union-Findの処理はほぼO(M)です。全ての辺を組み合わせる素朴解より、制約内で安定して処理できます。

MST・SCC・フローの学ぶ順番

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

まず解く

問題	公式解説	出題意図	difficulty
ABC429 B N – 1	公式解説	公式Editorialの方針を n minus one graph として整理する。	-725
ABC276 B Adjacency List	公式解説	Build each vertex’s sorted neighbor list from the undirected edge list.	-11
ABC442 C Peer Review	公式解説	Build the peer-review relation and check all consistency constraints.	67
ABC393 C Make it Simple	公式解説	Count self-loops and duplicate undirected edges; removing one edge from each makes the graph simple.	98
ABC455 C Vanish	公式解説	Match vanishing items greedily and count the unmatched remainder.	143

次に解く

問題	公式解説	出題意図	difficulty
ABC313 B Who is Saikyo?	公式解説	The unique vertex with indegree zero is the strongest player.	147
ABC376 C Prepare Another Box	公式解説	玩具と箱を大きさ順に突き合わせ、追加する箱を一つだけ許した最小サイズを判定する。	364
ABC404 C Cycle Graph?	公式解説	公式Editorialの方針を cycle graph degree check として整理する。	370
ABC464 C Plumage Palette	公式解説	Color the plumage graph and count compatible palettes.	400
ABC292 D G. Unicyclic Components	公式解説	各連結成分で頂点数と辺数が等しいかを調べ、単一閉路成分だけか判定する。	579

挑戦問題

問題	公式解説	出題意図	difficulty
ABC427 C Bipartize	公式解説	公式Editorialの方針を bipartite graph check として整理する。	629
ABC285 D G. Change Usernames	公式解説	Build a directed mapping of old to new usernames and reject if it contains a cycle.	663
ABC416 D Match, Mod, Minimize 2	公式解説	公式Editorialの方針を matching mod min dp として整理する。	682
ABC232 C Graph Isomorphism	公式解説	頂点対応の全順列を試し、各辺の有無が一致する写像があるか調べる。	685
ABC327 D G. Good Tuple Problem	公式解説	Build the conflict graph and test bipartiteness with BFS coloring.	709