この問題はトポロジカルソートの練習問題です。

各タスクを頂点とみなし、\((A_i,B_i)\) の組について \(A_i\) から \(B_i\) への有向辺がはられた有向グラフを考えます。この有向グラフにおいて、\((1,2,\ldots,N)\) の順列 \(P\) であって、\(P_j=A_i,P_k=B_i\) が成り立つならば \(j<k\) が成り立つような \(P\) のうち辞書順最小のものを求める問題です。

辞書順最小でなくとも、条件をみたすような \(P\) を求めることをトポロジカルソートといいます。トポロジカルソートするアルゴリズムとして有名なものは以下のようなものです。

• \(P\) を空の列とする。
• \(S\) を入次数が \(0\) であるような頂点の集合とする
• \(S\) が空でない間以下を繰り返す
  • \(S\) の任意の頂点 \(v\) を削除して \(L\) の末尾に追加する。
  • \(v\) から出る辺についてその辺を削除する。削除した各辺についてもう一方の端点が辺の削除によって入次数が \(0\) になった場合、その頂点を \(S\) に追加する。

この後、\(P\) の大きさが元のグラフの頂点数と一致しない場合はトポロジカルソートは不可能です。

この、\(S\) から頂点 \(v\) を選ぶ各段階では一般のトポロジカルソートではどのように \(v\) を選んでもよいです。そのため、今回の問題においては \(P\) を辞書順最小化したいため、\(S\) の最小値を選ぶのが最適です。

\(S\) を優先度付きキューにすることで \(\mathrm{O}(M+N\log N)\) 時間で計算することができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> ord;
    vector<int> deg(n);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].emplace_back(b);
        deg[b]++;
    }
    priority_queue<int, vector<int>, greater<>> pq;
    for (int i = 0; i < n; ++i)
        if (deg[i] == 0) pq.emplace(i);
    while (!pq.empty()) {
        auto v = pq.top();
        pq.pop();
        ord.emplace_back(v);
        for (auto u : g[v]) {
            deg[u]--;
            if (deg[u] == 0) pq.emplace(u);
        }
    }
    if (ord.size() != n) {
        cout << -1 << endl;
        return 0;
    }
    for (auto& e : ord) e++;
    for (int i = 0; i < n; ++i) cout << ord[i] << " \n"[i == n - 1];
}