[일반] DAG에서 위상정렬 했을 때 고정된 자리에 있는 원소 하나를 찾는 법?

[익명(37.19)]

간단한 답은 DAG와 inv DAG에서 reachability 판정을 한 것의 합집합이 정점 전체 집합일 때 그 정점인데

edge를 뒤집어야 하는 점에서 상수가 좀 커지고, 공간 면에서도 약간 비효율적일 것 같음.

이거보다 더 효율적인 방법이 있을까?

[익명(37.19)]

일단 이대로 짜놓고 생각나면 바꿔야겠네

[dpk(irc2265)]

혹시
https://www.acmicpc.net/problem/12823
이거인가

[익명(37.19)]

맞긴 한데 문제를 풀고 있지는 않았음 근데 방금 누가 큐에 원소 하나 남았을 때라고 댓글 달았었는데 그게 맞는 것 같다

[dpk(irc2265)]

https://koosaga.com/204
여기 풀이잇음

[익명(37.19)]

깔끔하네 ㄱㅅㄱㅅ 그리고 큐는 좀 더 생각해보니 안 되는 경우가 많음