「頂点 \(1\) を通る辺数が最小の閉路」がどのような性質を持つのか考えてみましょう。

頂点 \(1\) を通る辺数が最小の閉路のうちの \(1\) つが頂点 \(1\) \(\to\) 頂点 \(v_1\) \(\to\) 頂点 \(v_2\) \(\to\) \(\dots\) \(\to\) 頂点 \(v_k\) \(\to\) 頂点 \(1\) という形の \(k+1\) 辺からなる閉路だとします。この時、頂点 \(v_k\) に注目すると次の事実が証明できます。

頂点 \(1\) から頂点 \(v_k\) への距離は \(k\) である。

(証明) 頂点 \(1\) \(\to\) 頂点 \(v_1\) \(\to\) 頂点 \(v_2\) \(\to\) \(\dots\) \(\to\) 頂点 \(v_k\) というパスは長さ \(k\) なので頂点 \(1\) から頂点 \(k\) の距離は高々 \(k\) である。また、もしも長さ \(k\) 未満のパスが存在すると仮定すると、そのパスに頂点 \(v_k\) \(\to\) 頂点 \(1\) を加えて出来る閉路は頂点 \(1\) を含む \(k+1\) 辺未満の閉路となり、元の閉路が辺数が最小の閉路であるという仮定に矛盾する。よって示された。(証明終わり)

この事実から、辺数が最小の閉路を求めるには頂点 \(1\) から各頂点の最短距離が重要そうだとわかります。このような方向性で考察を進めると、次の事実が分かります。

頂点の集合 \(S\) を、頂点 \(v\) であって以下の条件をすべて満たすものからなる集合として定義する。

• 頂点 \(1\) から頂点 \(v\) へ到達可能である。
• 頂点 \(v\) から頂点 \(1\) へ向かう辺が存在する。

この時、問題の答えは次のようになる。

• \(S\) が空集合である場合、答えは解なしである。
• \(S\) が空集合でない場合、答えは \(\min_{v \in S} (頂点\ 1\ から頂点\ v\ への距離)\) に \(1\) を加えたものになる。

正当性は、閉路における頂点 \(1\) の \(1\) つ前の頂点を \(v\) とした時、先の証明の通り頂点 \(1\) から頂点 \(v\) までの距離に \(1\) を加えたものが辺数が最小の閉路になることから証明できます。

以上の議論により、BFS(幅優先探索) を用いて各頂点への最短距離を計算するアルゴリズムが正当な解法になります。具体的には以下のような処理を行います。

• BFS を用いて各頂点への距離を距離の昇順に計算する。BFS の内部では、通常の距離を計算する処理に加えて次の処理を行う。
  • 現在見ている頂点を \(c\) とする。頂点 \(c\) から頂点 \(1\) へ向かう辺が存在する場合は、頂点 \(1\) から頂点 \(c\) への距離に \(1\) を加えたものを答えとして出力して、全ての処理を終了する。
• 答えを出力しないまま BFS が終了した場合は、閉路が存在しないことになるので -1 を出力する。

このアルゴリズムは \(\mathrm{O}(N + M)\) で動作して十分高速です。

• 実装例 (Python)

from collections import deque

N, M = map(int, input().split())
g = [list() for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)

inf = 10**9
d = [inf] * N
Q = deque()

d[0] = 0
Q.append(0)

while len(Q) > 0:
    cur = Q.popleft()
    for dst in g[cur]:
        if dst == 0:
            print(d[cur] + 1)
            exit()
        if d[dst] == inf:
            d[dst] = d[cur] + 1
            Q.append(dst)

print(-1)