Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 0519 - Worst Sportswriter

問題文 : 最悪の記者

解法 :
トポロジカルソートをすればよい.
トポロジカル順序が複数あるかどうかは, 隣り合う2 つの順位について, 互いへ直接たどり着けるかどうかを判定すれば良い.
(隣り合う順位へ直接辿りつけないのであれば, その2 つを仲介する順位が存在するからこれでよい.)

トポロジカルソートにO(m), 互いへたどり着けるかの判定がO(m)で, 計O(m) 時間でこの問題を解くことが出来る.

#include <cstdio>
#include <vector>

using namespace std;

bool other;
bool vis[5000];
vector<int> win[5000], lose[5000], ord;

void dfs(int v)
{
	vis[v] = true;
	for (int i = 0; i < win[v].size(); i++){
		if (!vis[win[v][i]]) dfs(win[v][i]);
	}
	ord.push_back(v);
}

int main()
{
	int n, m;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < m; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		win[--a].push_back(--b);
		lose[b].push_back(a);
	}
	
	int cnt = 0;
	for (int i = 0; i < n; i++)
		if (lose[i].size() == 0) dfs(i);
	
	for (int i = n - 1; i >= 0; i--){
		printf("%d\n", ord[i] + 1);
		if (i){
			bool ok = true;
			for (int j = 0; j < win[ord[i]].size(); j++)
				if (win[ord[i]][j] == ord[i - 1]) ok = false;
			other |= ok;
		}
	}
	printf("%d\n", other);
	
	return (0);
}