BOJ 19760 Операция <<Перестановка>>

문제 링크입니다.

문제 요약

길이 $N$의 순열 $A$에 관한 $M$개의 정보가 순서대로 주어집니다. 각 정보는 $x\ y$ 꼴로 주어지며, 이는 $A[x] < A[y]$를 의미합니다.

몇 번째 정보까지 주어졌을 때 처음으로 $A$를 유일하게 결정할 수 있게 되는지 구하세요.

풀이

$A[x] < A[y]$를 간선 $x \rarr y$로 치환합시다. $A$를 유일하게 결정하려면 이렇게 구성된 그래프의 위상 정렬 결과가 유일하게 결정되어야 합니다. 그렇지 않으면 중간에 두 원소의 순서를 바꿔도 모든 조건을 만족시킬 수 있는 경우가 생기기 때문입니다.

위상 정렬 결과가 유일하게 결정되려면 어떤 원소에서 바로 다음 원소로 가는 간선이 있어야 합니다. 역으로 이런 간선들만 있어도 위상 정렬 결과가 유일하게 결정되기 때문에, 이 간선들이 모두 갖춰지는 때를 찾으면 전체 문제를 시간 복잡도 ${\cal O}(N+M)$에 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;

vector<pii> e[101010];
int deg[101010];

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int u, v; cin >> u >> v;
		e[u].push_back({v,i});
		deg[v]++;
	}
	queue<int> q; int ans = 0;
	for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i);
	while(q.size()){
		if(q.size() > 1) return !(cout << -1);
		int now = q.front(); q.pop();
		for(auto [nxt, idx] : e[now]){
			deg[nxt]--;
			if(!deg[nxt]){
				ans = max(ans, idx);
				q.push(nxt);
			}
		}
	}
	cout << ans;
}