ABC142-F Pure 解説

$O(N+M)$ で解きます。

問題

AtCoder Beginner Contest 142 | F - Pure

概要

$N$ 頂点 $M $ 辺の有向グラフが与えられる。極小のサイクルを一つ見つけよ。

解法

問題文に書かれている条件は「概要」のように言い換えることができます。 editorial では

1. 最小のサイクルを見つける
2. サイクルを一つ見つけ、どんどん小さくしていく

の二通りの方法で解いており、どちらも計算量は $O(N(N + M))$ です。

このうち後者の方法は

• サイクルを一つ見つける
• ショートカットができる限り、より小さなサイクルに更新していく

の二つのステップからなっています。この解法をベースに進めていきます。

サイクルを一つ見つける

このパートは特に工夫は要りません。 「有向グラフ サイクル 検出」などで検索するとたくさん出てくるので調べてみてください。 深さ優先探索を行うだけではありますが、非再帰で実装するのはちょっとだけ大変です。 計算量は $O(N + M)$ です。

小さなサイクルに更新していく

準備として、

$$ \begin{aligned} \mathit{used}[v] &= \begin{cases} \mathrm{true} & \text{(頂点 $v$ がサイクルに使われている)} \\ \mathrm{false} & \text{(使われていない)} \end{cases} \\ \mathit{next}[v] &= \text{サイクル上で $v$ の次の頂点} \end{aligned} $$

であるような配列 $\mathit{used}, \mathit{next}$ を作っておきます。サイクルに使われていない頂点は $\mathit{next}$ に何が入っていてもいいこととします。サイクルの長さは高々 $N$ なので、これらの配列は $O(N)$ で計算可能です。

準備ができたら、辺を順番に見ていきます。辺 $uv$ について $\mathit{used}[u] = \mathrm{true}, \mathit{used}[v] = \mathrm{true}, \mathit{next}[u] \neq v$ であるような時は、下図のような状況です。

このように、 $u$ から $v$ への経路を辺 $uv$ に置き換えることで、より小さなサイクルを作ることができます。ここでの更新処理が重要で、 サイクル上で $u$ から $v$ の間にある頂点の $\mathit{used}$ を $\mathrm{false}$ にする という処理を行います。もちろん $\mathit{next}[u]$ の更新も忘れずに行ってください。

サイクルを縮める操作は何度か行う可能性がありますが、この方法では一度 $\mathrm{false}$ になった頂点はその後処理の対象となりません。そのため、全ての辺に対する処理は合計しても $O(N+M)$ で済みます。 一方、$v$ から $u$ へと辿ってサイクルを再構成しようとすると、サイクルの大きさが $N \to N-1 \to N-2 \to \cdots$ と変化するような場合に $O(N ^ 2)$ かかってしまいます。

また、この処理の過程でサイクルに新たな頂点が追加されることはないので、それまでショートカットに使えなかった辺が新しく使えるようになることはありません。 なので、順番を気にすることなく全ての辺を一回ずつ見るだけで、それ以上のショートカットが不可能な極小のサイクルを得ることができます。

計算量は全体で $O(N+M)$ です。

実装

提出コード (Python)

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]

G = [list() for _ in range(N+1)]
for (u, v) in edges:
  G[u].append(v)

# サイクル検出
seen = [-1]*(N+1)
# -1: 未到達
# 0: stack追加済み
# 1: 行きがけで通過済み(cycle候補)
# 2: 帰りがけで通過済み
curr_path = []
stack = []

def dfs():
  for i in range(1, N+1):
    if seen[i] == 2:
      continue
    stack.append(i)
    while stack:
      u = stack.pop()
      if u > 0: # 行きがけ
        stack.append(-u)
        curr_path.append(u)
        seen[u] = 1
        for v in G[u]:
          if seen[v] == -1:
            seen[v] = 0
            stack.append(v)
          elif seen[v] == 1:
            cycle = curr_path[curr_path.index(v):]
            return cycle
      else: # 帰りがけ
        seen[-u] = 2
        curr_path.pop()
  return list()

cycle = dfs()
if not cycle:
  print(-1)
  exit()

# サイクルを小さくする
# 準備
used = [False] * (N+1)
next = [0] * (N+1)
for i in range(len(cycle)):
  used[cycle[i]] = True
  next[cycle[i-1]] = cycle[i]

# ショートカットできるか確かめる
for (u, v) in edges:
  if used[u] and used[v] and next[u] != v:
    w = next[u]
    while w != v:
      used[w] = False
      w = next[w]
    next[u] = v

# サイクル復元
u = used.index(True)
ans = [u]
v = next[u]
while v != u:
  ans.append(v)
  v = next[v]

print(len(ans))
for x in ans:
  print(x)

余談

提出コード

ウケますね