mayoko’s diary

プロコンとかいろいろ。

AOJ 0519: Worst Reporter

解法

順位表の再現はトポロジカルソートをすれば簡単にできます。あとは複数通りのトポロジカルソートがあり得るかですが, ここでトポロジカルソートのアルゴリズムを見てみましょう。

L ← トポロジカルソートした結果を蓄積する空リスト
S ← 入力辺を持たないすべてのノードの集合

while S が空ではない do
    S からノード n を削除する
    L に n を追加する
    for each n の出力辺 e とその先のノード m do
        辺 e をグラフから削除する
        if m がその他の入力辺を持っていなければ then
            m を S に追加する

if グラフに辺が残っている then
    閉路があり DAG でないので中断

(wikipedia から)

これを見ると, 複数通りのトポロジカルソートがあり得るのは「ある瞬間に S に複数の要素がある場合」であるとわかります。

ところで当たり前といえば当たり前なんですが上のアルゴリズムは閉路検出のアルゴリズムに似ています。
mayokoex.hatenablog.com

// トポロジカルソートする
void TopologicalSort(const vector<vi>& G, vi& order, int& flag) {
	int n = G.size();
	vector<int> degree(n);
	for (int v = 0; v < n; v++) {
		for (int u : G[v]) 
			degree[u]++;
	}
	flag = 0;
	queue<int> que;
	for (int i = 0; i < n; i++) {
		if (degree[i] == 0) {
			que.push(i);
		}
	}
	while (!que.empty()) {
		flag |= (que.size() > 1);
		int now = que.front(); que.pop();
		order.push_back(now);
		for (int ch : G[now]) {
			if (degree[ch] == 0) continue;
			if (--degree[ch] == 0) {
				degree[ch] = 0;
				que.push(ch);
			}
		}
	}
	reverse(order.begin(), order.end());
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<vi> G(n);
    for (int i = 0; i < m; i++) {
    	int a, b;
    	cin >> a >> b;
    	a--; b--;
    	G[b].push_back(a);
    }
    vi order;
    int flag = 0;
    TopologicalSort(G, order, flag);
    for (int i = 0; i < n; i++) 
    	cout << order[i]+1 << endl;
    cout << flag << endl;
    return 0;
}