問題概要

$1, 2, \dots, N$ の順列であって、以下の $M$ 個の条件を満たすもののうち、辞書順最小のものを求めよ。

【 $i$ 番目の条件】
$A_{i}$ は $B_{i}$ よりも先に来る

制約

$N, M \le 2 \times 10^{5}$

考えたこと

グラフの問題として考えてみよう。頂点番号が $1, 2, \dots, N$ であるグラフを用意して、頂点 $A_{i}$ から頂点 $B_{i}$ へと有向辺を張っていく。頂点数 $N$ 、辺数 $M$ の有向グラフとなる。

もしこのグラフが有向サイクルを持つ場合は、答えは -1 となる。
このグラフが有向サイクルを持たない場合は「辞書順最小なトポロジカルソート順を求めよ」という問題となる。

これらの処理をまとめて行うには、キューを用いた後退解析をしていくとよいだろう。ただし、キューといっても、優先度付きキュー (que とする) を用いる。que は、グラフの頂点番号を挿入していくものとして、頂点番号が最小のものを取り出してくれるような優先度付きキューとする。

最初に、入次数が 0 である頂点をすべてキューに挿入する
キューが空になるまで、以下を繰り返す:
- キューから頂点 $v$ を取り出して、答えを表す配列 res の末尾に挿入する
- 頂点を始点とする各辺について:
  - 頂点 $w$ の入次数を 1 減らす（ $v$ を破壊するため）
  - もし $w$ の入次数が 0 になるならば、 $w$ をキューに挿入する
- 頂点 $v$ をグラフから削除する（実装上は何もしなくてよい）

キューが空になったとき、もしグラフにサイクルが残っていたら（キューから取り出された頂点の個数が $N$ 未満であったら）、-1 を出力しよう。

そうでなければ、配列 res の要素を先頭から順に出力しよう。

計算量

$O(M + N \log N)$

コード

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

int main() {
    int N, M, A, B;
    cin >> N >> M;
    vector<vector<int>> G(N);
    vector<int> deg(N, 0);
    for (int i = 0; i < M; i++) {
        cin >> A >> B, A--, B--;
        G[A].push_back(B);
        G[B].push_back(A);
        deg[B]++;
    }

    vector<int> res;
    priority_queue<int, vector<int>, greater<int>> que;
    for (int v = 0; v < N; v++) {
        if (deg[v] == 0) que.push(v);
    }
    while (!que.empty()) {
        auto v = que.top();
        que.pop();
        res.push_back(v+1);
        for (auto v2 : G[v]) {
            deg[v2]--;
            if (deg[v2] == 0) que.push(v2);
        }
    }
    if (res.size() < N) cout << -1 << endl;
    else {
        for (auto val : res) cout << val << " ";
        cout << endl;
    }
}