Pure [AtCoder Beginner Contest 142 F]

https://atcoder.jp/contests/abc142/tasks/abc142_f

• BFS

解説

https://atcoder.jp/contests/abc142/submissions/7770966

まず、どこから手を付けようかという感じであるが、NもMも制約がゆるい。
うーん。
作りたいグラフはサイクルである。
サイクルだけのグラフを作りたい。
これ枝刈り全探索通るのでは？
いや、1つ閉路を見つけて、そこから最小化していけばいい？
いや、最小のサイクルを探せばいいのか。

最小のサイクルを探す。
もし、あればそれが答え。
辺に注目すると、a->bの辺を削除した上で、bからaへの最短距離を計算する。
これで、a->b->...aのサイクルとその長さが得られる。
この長さが最小のものが答え。サイクルを復元していこう。
最短経路はBFSで計算可能。

int N, M, A[2020], B[2020];
vector<int> E[1010];
bool vis[1010];
int dist[1010], back[1010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    int mi = inf;
    vector<int> ans;
    rep(er, 0, M)
    {
        rep(i, 0, N) E[i].clear();
        rep(i, 0, M) if (er != i) E[A[i]].push_back(B[i]);
        int st = A[er];
        int gr = B[er];

        rep(i, 0, N) {
            vis[i] = false;
            dist[i] = 0;
        }

        queue<int> que;
        que.push(gr);
        vis[gr] = true;
        dist[gr] = 0;

        while(!que.empty()) {
            int cu = que.front();
            que.pop();
            fore(to, E[cu]) if(!vis[to]) {
                vis[to] = true;
                dist[to] = dist[cu] + 1;
                back[to] = cu;
                que.push(to);
            }
        }

        if (!vis[st]) continue;

        int len = dist[st] + 1;
        if (chmin(mi, len)) {
            ans.clear();

            int x = st;
            while(x != gr) {
                ans.push_back(x);
                x = back[x];
            }
            ans.push_back(gr);
        }
    }

    if (mi == inf) {
        cout << -1 << endl;
        return;
    }

    sort(all(ans));

    int K = ans.size();
    printf("%d\n", K);
    fore(i, ans) printf("%d\n", i + 1);
}