백준 9466번 링크 문제 풀이 Cycle을 찾는다는 점에서 그래프 문제처럼 생겼지만, 그래프 형태가 워낙 단순해서 스택 문제라고 생각해도 될 것 같다. 사실 DFS나 스택이나 뭐... 같은 방식이니 다른 분들과 다 비슷하게 푼 것 같다. 각 vertex는 directed edge를 하나씩만 가지므로 그래프도 단순하게 int형 배열로 선언한다. visited를 int형으로 선언한 것이 이 문제를 풀 때 유일한 아이디어?라고 할 수 있을 것 같다. 모든 vertex가 연결되어 있지 않은 그래프에서, 모든 vertex에 대해서 DFS를 진행할 때 각 vertex를 방문한 적이 있는지 확인한다. 이때, cnt라는 int형 변수의 값을 1씩 증가시키고, 이번 DFS에서 방문하는 모든 점들의 visited 값은 cnt로 설정한다. 이렇게 하면 몇번째 DFS에서 방문된 vertex인지 확인이 가능하다. Cyc

링크텍스트 풀이 방법 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