JOI 2007 本選4 最悪の記者 - 解説

アルゴリズム

• トポロジカルソート

問題

D - 最悪の記者

n個のチームが総当たりのリーグ戦をした

一部の試合の勝敗(m個)が与えられるのでチームの順位を求めよ、また、複数の答えが考えられる場合その旨を報告せよ

1≤n≤5000, 1≤m≤100000

グラフで捉える

「aチームがbチームに勝った」などは依存関係と捉えることができ、グラフに帰着できます

したがって、チームを頂点として

「aチームがbチームに勝った」→ aからbへ辺を張る

とすることでグラフを構築できます

トポロジカルソート

この問題はチームの勝敗(依存関係)を整理することで答えを求めることができます

つまりトポロジカルソートで答えを求めることができます

複数解がある場合の判定

トポロジカルソートの最中に入次数が0の頂点が2つ以上同時に現れるとトポロジカルソートの答えが複数出てきます

つまりこの問題の答えも複数出てくることになります

したがって、複数解があるかどうかの判定はトポロジカルソート中に入次数0の頂点が同時に現れるかどうか調べることで判定できます

したがって

トポロジカルソートの計算量よりこの問題を

O(n + m)で解くことができます

コード

▼ C++のサンプルコード(include defineは省略)

using Graph = vvi;
 
bool flag = false;
 
vector topological_sort(vector<vector> &G, vector &indegree, int V) {
	priority_queue<int, vector, greater<>> Q; //降順プライオリティキュー
	vector seen(V, false);
	vector order;
	order.clear();
	for (int i =0; i < V; i++)
		if (indegree[i] == 0)//入次数が0
			Q.push(i);
	while (!Q.empty()) {
		if (Q.size() > 1)
			flag = true;
		int v = Q.top();
		Q.pop();
		seen[v] = true;
		order.push_back(v);
		for (auto next : G[v]) {
			if (seen[next])
				continue;
			indegree[next]--;//辺を取り除く
			if (indegree[next] == 0)//入次数が0になった
				Q.push(next);
		}
	}
	bool flag = false;
	for (int i = 0; i < V; i++)
		if (indegree[i] != 0)
			flag = true; //DAGではない
	if (flag)
			//DAGではない時は-1のみの配列を返す
		return {-1};
	else
			//トポロジカルソート順(いくつかある中で昇順で一番初めのものを返す)
		return order;
}
 
void Main() {
	int n;
	cin >> n;
	int m;
	cin >> m;
	Graph G(n);
	vi indegree(n, 0);
	rep(i, m) {
		int a, b;
		cin >> a >> b;
		a--;b--;
		G[a].pb(b);
		indegree[b]++;
	}
	vi order = topological_sort(G, indegree, n);
	rep(i, order.size()) cout << order[i] + 1 << endl;
	cout << (flag ? 1 : 0) << endl;
}

筆者の提出atcoder.jp

「グラフに帰着できる」と思いつけるかどうかが肝の問題でした

勝敗を依存関係として捉えるのがポイントです