実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 743

問題概要

頂点に $1$ から $N$ の番号がついた $N$ 頂点 $M$ 辺の単純有向グラフがあります。 $i$ 番目の辺は頂点 $a_i$ から頂点 $b_i$ へ伸びる辺である。頂点 $1$ を含む閉路が存在するか判定して、存在する場合はそのような閉路のうち辺数が最小の閉路の辺数を求めよ。

制約

入力は全て整数。
$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5 \right)$

考察

閉路を検出するだけならいつもの DFS / BFS のアルゴリズムに少し手を加えることで実現できるが、本問ではその中で最小の閉路を要求されている。

ここで、「頂点 $1$ を含む閉路を全て求める」のではなくて、「ある頂点から頂点 $1$ に戻ってくることができるか」を考えることにしよう。この「ある頂点」を「頂点 $1$ と直接つながっている頂点」とすることで、以下のアルゴリズムが構築できる。

頂点 $1$ からの頂点 $v$ までのパスの長さを格納する配列 $\mathrm{dist}_v$ と、 BFS の際に使用することになる、次の探索頂点を格納しておくqueueを用意する。なお、 $\mathrm{dist} = \infty$ と初期化しておく。
頂点 $1$ と直接つながっている頂点群を $V' = (v'_1, v'_2, \cdots, v'_k)$ とするとき、 $\mathrm{dist}_{v'_i} = 1 \: (1 \leq i \leq k)$ としてqueueに挿入する。
queueの先頭の頂点から BFS を実行する。
探索が終了したのち、
- $\mathrm{dist}_1 = \infty$ ならば、頂点 $1$ を含む閉路は存在しなかったことになるので、-1を出力する。
- そうでないならば、 $\mathrm{dist}_1$ が頂点 $1$ を含む閉路の中で最小のものの長さとなる。

あとはこれをコードに落とし込めばよい。なお、以下のコードは頂点の番号が 0-indexed である。

コード

#include <bits/stdc++.h>
using namespace std;

template <class T>
using Graph = vector<vector<T>>;

constexpr auto INF = 1e+9;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, M;
    cin >> N >> M;
    Graph<int> G(N);
    vector<int> dist(N, INF);
    queue<int> que;
    rep(i, 0, M)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;

        if (a == 0)
        {
            que.push(b);
            dist[b] = 1;
        }
        else
        {
            G[a].push_back(b);
        }
    }

    while (!que.empty())
    {
        int v = que.front();
        que.pop();

        for (auto next : G[v])
        {
            if (dist[next] == INF)
            {
                dist[next] = dist[v] + 1;
                que.push(next);
            }
        }
    }

    if (dist[0] == INF)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << dist[0] << endl;
    }
}