問題
有向グラフ（$N$ 頂点 $M$ 辺）に対し、オイラー閉路（全辺をちょうど1回通り始点=終点）の判定・辺番号列の出力（辞書順最小）・存在しない場合の最小追加辺数を求めよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 10^5$ |
| $M$ | $1 \le M \le 2 \times 10^5$ |
| グラフ | 弱連結・多重辺あり |
入出力例
入力例 1
4 6
1 2
2 3
3 1
1 3
3 4
4 1出力例 1
Yes
1 2 3 4 5 6入力例 2
3 4
1 2
2 3
3 1
1 2出力例 2
No
1例2: 頂点1の出次数=2,入次数=1（差=+1）。頂点3の出次数=1,入次数=2（差=-1）。差の正和=1 → 辺1本追加で解決。
概念図: Hierholzer法の動作
ヒント（段階的開示）
ヒント1: 方向性
有向グラフのオイラー閉路の存在条件：全頂点で「出次数 = 入次数」かつ弱連結。条件を満たさない場合は正差の頂点から負差の頂点への辺追加が最小。
ヒント2: アプローチ
- 各頂点の $(d_v = \text{out}(v) - \text{in}(v))$ を計算
- $\sum_{d_v > 0} d_v$ = 追加辺数（= $\sum_{d_v < 0} |d_v|$）
- Hierholzer法: スタックベースで反復実装、辺を min-heap 管理
- 結果リストを最後に逆順にして出力
ヒント3: コード骨格
import heapq
graph = [[] for _ in range(N+1)]
for i, (u, v) in enumerate(edges):
heapq.heappush(graph[u], (i+1, v))
stk = [start]
edge_stk = []
result = []
while stk:
v = stk[-1]
if graph[v]:
eid, u = heapq.heappop(graph[v])
stk.append(u)
edge_stk.append(eid)
else:
stk.pop()
if edge_stk:
result.append(edge_stk.pop())
result.reverse()
print(' '.join(map(str, result)))模範解答 (Python)
import sys
import heapq
input = sys.stdin.readline
def solve():
N, M = map(int, input().split())
edges = []
out_deg = [0] * (N + 1)
in_deg = [0] * (N + 1)
graph = [[] for _ in range(N + 1)]
for i in range(M):
u, v = map(int, input().split())
edges.append((u, v))
heapq.heappush(graph[u], (i + 1, v))
out_deg[u] += 1
in_deg[v] += 1
# 次数チェック
pos_sum = sum(max(0, out_deg[i] - in_deg[i]) for i in range(1, N+1))
if pos_sum > 0:
print("No")
print(pos_sum)
return
# 辺が存在する最小頂点からスタート
start = 1
for v in range(1, N + 1):
if out_deg[v] > 0:
start = v
break
# Hierholzer法
stk = [start]
edge_stk = []
result = []
while stk:
v = stk[-1]
if graph[v]:
eid, u = heapq.heappop(graph[v])
stk.append(u)
edge_stk.append(eid)
else:
stk.pop()
if edge_stk:
result.append(edge_stk.pop())
result.reverse()
if len(result) != M:
print("No")
print(-1)
return
print("Yes")
print(' '.join(map(str, result)))
solve()Step-by-Step 解説
Step 1: オイラー閉路の存在条件
| 条件 | 内容 |
|---|---|
| 次数条件 | 全頂点で 出次数 = 入次数 |
| 連結条件 | 辺が存在する頂点の集合で強連結 |
Step 2: 最小辺追加数
$d_v = \text{out}(v) - \text{in}(v)$ を計算。$d_v > 0$ の頂点から $d_v < 0$ の頂点へ辺を追加することでバランスを取る。追加辺数 $= \sum_{d_v > 0} d_v$（常に $= \sum_{d_v < 0} |d_v|$）。
Step 3: Hierholzer法の原理
スタックに頂点を積み、未使用辺があれば辺を取って次頂点を push。辺がなければ pop してその頂点の直前の辺を result に追加。最後に逆順にすることでオイラー閉路の辺番号列が得られる。
Step 4: 辞書順最小の保証
各頂点の隣接リストを辺番号の min-heap として管理し、常に最小番号の辺を選択する。
Step 5: 計算量
| 操作 | 計算量 |
|---|---|
| 次数計算 | $O(M)$ |
| Hierholzer法 | $O(M \log M)$ |
| 全体 | $O(M \log M)$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 辺番号の追跡ミス | edge_stk と stk を同期させない | 辺を取るときに edge_stk にも push |
| 逆順出力忘れ | Hierholzer は逆順で辺を result に積む | result.reverse() を必ず実行 |
| スタート頂点の選択 | 孤立頂点からスタート | 出次数 > 0 の最小頂点を選ぶ |
| 全辺を通ったか確認 | 非連結時に一部の辺を見落とす | len(result) != M なら Error |
次のステップ
発展問題: 無向グラフのオイラー路（奇数次数頂点が2つの場合）。関連: 中国人郵便配達問題（奇数次数頂点の最小重みマッチング + オイラー閉路）。