scc1 SCC SCC : 강한 연결 요소 strongly connected components 그래프 내 vertex 중 서로 간의 경로가 양방향 모두 존재하는 vertex들의 집합 X⊂G s.t. ∀a, b∈X, ∃ paths both a→b, b→a DFS와 스택이 핵심이다. 방문 지점의 order(몇 번째로 방문했는지)를 이용한다. DFS함수의 리턴 값은 현재 노드에서 도달할 수 있는 지점 중 가장 먼저 방문한 지점의 방문 순서이다. DFS(cur) = par = cur에서 도달할 수 있는 지점의 ord 중 최솟값 ord[v] v 방문 순서 fin[v] v 방문 완료 여부 = v가 속하는 SCC를 찾았는지? 현재 방문한 지점을 cur, 다음에 방문할 지점을 nxt라 하자. nxt는 다음 세 가지 경우 중 하나에 .. 2021. 4. 13. 이전 1 다음
