問題概要

頂点数 $N$ 、辺数 $M$ の DAG (閉路のない単純有向グラフ) が与えられる。

このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。

制約

$1 \le N \le 5000$
$1 \le M \le 10^{5}$

考えたこと

まずトポロジカルソート自体は次の記事に書いた！

DFS でやるやつ

qiita.com

BFS でやるやつ

qiita.com

一意性の方をちょっと考えてみよう！

トポロジカルソートが一意となる条件とは

まずトポロジカルソートとは、下図のように、各頂点を辺の向きに沿うように一列に並べることである。

上の並び替え方は一意ではない。下図のような並び替え方もできる。

一般に、トポロジカルソート順 $v_{1}, v_{2}, \dots, v_{N}$ において、ある連続する 2 要素 $v_{i}, v_{i+1}$ の間に辺がないとき、その 2 要素を入れ替えることができてしまう！！！！！

逆に、すべての連続する 2 要素 $v_{i}, v_{i+1}$ の間に辺があるとき、順序が一意に確定する！！！！！！

よって、解法としては以下のとおり。

トポロジカルソート順を 1 つ求める
その順序に沿って辺がすべてあるかどうかを判定する

計算量は $O(N+M)$ 。

コード 1 (DFS バージョン)

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    set<pint> edges;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[u].push_back(v);
        edges.insert(pint(u, v));
    }

    // ord: 実際に並び替えられた順序
    vector<int> ord, seen(N, false);
    auto dfs = [&](auto self, int v) -> void {
        seen[v] = true;
        for (auto nv: G[v]) if (!seen[nv]) self(self, nv);
        ord.push_back(v);
    };
    for (int v = 0; v < N; ++v) if (!seen[v]) dfs(dfs, v);
    reverse(ord.begin(), ord.end());

    // 出力
    bool unique = true;
    for (int i = 0; i+1 < ord.size(); ++i) {
        if (!edges.count(pint(ord[i], ord[i+1]))) unique = false;
    }
    for (auto v: ord) cout << v+1 << endl;
    cout << (unique ? 0 : 1) << endl;
}

コード 2 (BFS バージョン)

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using Graph = vector<vector<int>>;

int main() {
    int N, M;
    cin >> N >> M;
    Graph G(N);
    vector<int> deg(N, 0); // 出次数
    set<pint> edges;
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        G[v].push_back(u); // 逆向きに辺を張っておく
        deg[u]++;
        edges.insert(pint(u, v));
    }

    // 出次数が 0 の頂点から後退解析していく
    vector<int> ord, finished(N, false);
    queue<int> que;
    for (int v = 0; v < N; ++v) if (deg[v] == 0) que.push(v);
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        finished[v] = true;
        ord.push_back(v);
        for (auto nv: G[v]) {
            if (finished[nv]) continue;
            deg[nv]--;
            if (deg[nv] == 0) que.push(nv);
        }
    }
    reverse(ord.begin(), ord.end());

    // 出力
    bool unique = true;
    for (int i = 0; i+1 < ord.size(); ++i) {
        if (!edges.count(pint(ord[i], ord[i+1]))) unique = false;
    }
    for (auto v: ord) cout << v+1 << endl;
    cout << (unique ? 0 : 1) << endl;
}