[질문] DAG가 주어졌을 때 위상정렬 위치가 확정된 노드 구하는 법 좀여

[맥콜리언(min2930)]

어떡하는지 모르겠어여 ㅠ

[익명(219.255)]

과제?ㅋ

[시아닌(kimjg1119)]

입차수와 출차수를 잘 따져보렴

[맥콜리언(min2930)]

출차수 고려를 어떻게 해야 풀 수 있나요? 위상정렬하면서 입차수 0 처리된거 에서 출차수 많은 순으로 힙차리해서 뽑아내야 되나여?

[맥콜리언(min2930)]

노드는 10만개 엣지는 100만입니다

[시아닌(kimjg1119)]

힌트를 좀 드리자면 위상정렬 할때 입차수가 0인 정점들을 지우는거잖아요

[시아닌(kimjg1119)]

근데 위치가 확정되려면 그 순간에 지워야 하는 노드가 확정되어야 한다는 얘기랑 똑같잖아요

[시아닌(kimjg1119)]

백준 3665 풀고오세요

[맥콜리언(min2930)]

문제는 보고 왔는데 기본 위상정렬 문제 같네요... 그 순간 지워야하는 노드가 정확히 하나인걸 판별을 어떻게해야할까요? 그냥 위상정렬로 했을 때 ( 3) (1 2) 1와 3이 입차가 0인 순간 어떻게 고르냐에 따라 2가 순번 결정된 노드라 판별가능하다는 문제가 았습니다.

[맥콜리언(min2930)]

3665번에선 이런경우 불가능이라 판별시켜버리기 때문에 고려 대상이 아닌거 같습니다. 제가 문제를 잘 못읽을 수도 있어 틀렸을 수도 있습니다.