Boj 3665) 최종 순위

문제

백준 3665

설명

인접행렬을 만들어 위상정렬을 돌려도 O(\(\mathrm{N}^2\)) 으로 충분히 돌아가지만, 선형시간에 해결할 수 있는 방법이 있어 기록한다.

먼저, 순위가 확실하게 정해지지 않는 경우는 존재하지 않는다는걸 알아야한다. 증명은 간단하다. 만약 a 와 b 가 어떤 정점 뒤에 와도 모순이 없다고 하자. 하지만 맨 처음에 전체순위가 주어졌으므로 a 와 b 사이에 대소관계가 존재한다. 즉 a 와 b 중 하나가 먼저와야하므로 모순이다. 그러므로 순위가 모호한 경우는 존재하지 않는다.

그러면 남는 경우는 순위를 정할 수 있거나 순위가 모순되거나 두가지 경우 뿐이다. 만약 모순이 되지 않는다면, 순서가 바뀌는 모든 경우를 준다고 했으므로 저번 순위와 이번 순위의 차이만큼 순서가 바뀌어 햔다. 다시말해, m 개의 순서쌍마다 순서를 반영해서 ++, -- 를 한 결과가 여전히 1부터 n 까지의 값을 가지고 있어야 모순이 아니라는 것이다. 이를 체크하면 답을 도출할 수 있다.

시간 복잡도

O(\(\mathrm{N} + \mathrm{M}\))

코드

int p2i[501]; // team 이 몇위냐
int ranks[501], ans[501];

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
		{
			int a;
			cin >> a;
			ranks[a]  = p2i[a] = ans[i] = i;
		}

		int m; cin >> m;		
		for (int i = 0; i < m; i++)
		{
			int a, b; cin >> a >> b;
			if (p2i[a] < p2i[b]) {
				ranks[a]++; ranks[b]--;
			}
			else {
				ranks[a]--; ranks[b]++;
			}
		}
	
		// Rank 를 기준으로 순위를 재정렬한다.
		sort(ans + 1, ans + n + 1, [](int a, int b) { return ranks[a] < ranks[b]; });
		
		bool bContra = false;
		for(int i = 1; i < n; i++)
			if (ranks[ans[i]] != ranks[ans[i + 1]] - 1)
			{
				bContra = true; break;
			}
	
		if (bContra) cout << "IMPOSSIBLE\n";
		else {
			for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
			cout << '\n';
		}
	
	}
}