백준 2623번 음악프로그램 순서를 정하는 문제에서 바로 topological sort라는 느낌이 왔다. SCC (Strongly Connected Component) Directed graph의 component 중 각 node로부터 다른 모든 node로 이동하는 경로가 있는 component를 SCC라 한다. Cycle이 있는 경우, cycle의 경로에 포함되는 node들의 집합을 SCC라 할 수 있다. SCC를 찾아내는 알고리즘에는 크게 세가지가 있다. Tarjan's algorithm Path-based algorithm Kosaraju's algorithm 이번 문제는 topological sort를 위해 SCC detection만 수행하면 되므로, 단순하게 dfs를 통해 cycle이 존재하는지만 확인하였다. Topological Sort SCC(Strongly

링크텍스트 풀이 방법 Topological sort를 이용한다. 각 학생을 vertex로 보고, 각 규칙을 directed edge로 볼 수 있다. 결과는 규칙을 만족하는 결과를 요구하므로, 모든 edge의 방향성을 만족하는 topological sort가 적절하다. Topological Sort Topological sort의 원리는 다음과 같다. SCC(Strongly connected component) detecting을 한다. SCC는 directed graph에서 모든 정점으로부터 다른 정점까지의 경로가 있는 정점의 집합을 의미한다. SCC 내에는 cycle이 있기 때문에, 모든 directed edge를 만족하는 순서에 따라 sort를 할 수 없다. 즉, SCC가 있는 경우에는 topological sort를 할 수 없다. DFS를 한다. DFS가 끝난 ve