백준 6543번 그래프의 싱크

사용한 알고리즘 : SCC

​

bottom(G) = {v ∈ V: ∀w ∈ V, (v→w) ⇒ (w→v)} 를 만족하는 v 들을 찾는 것이 문제였습니다.

즉 각 점들을 SCC 로 묶어서, outdegree (다른 SCC로 가는 edge 수) 가 0 인 SCC 를 찾으면 됐습니다.

먼저 DFS라는 함수를 만들어 SCC 를 만들어 주었습니다.

이후 모든 점들을 보면서,

어떤 점에서 그 점의 자손들(adj로 정리 해둔 자손들)이 자신과 같은 SCC 안에 있지 않은 경우,

그 점이 포함된 SCC (코드상 sn[i] : i가 속한 SCC) 의 outdegree++ 해주는 개념으로

그냥 해당 SCC를 없애버렸습니다.

(우리의 목적은 outdegree가 0인 SCC를 찾는 것이기 때문에 outdegree가 하나라도 있으면 답이 될 수 없다고 생각했습니다.)

​

이후 남은 SCC 들을 정렬하여 답을 냈습니다.