C++)백준_2150번 : SCC

타잔 알고리즘 풀이

Problem Link

Strongly Connected Components(SCC)
강결합요소는 모든 정점이 자신을 제외한
모든 정점에 대해 방문 가능한 요소이다.

SCC 알고리즘

• 코사라주 알고리즘
• 타잔 알고리즘

코사라주 알고리즘

• Graph와 Reverse Graph가
  같은 SCC를 가진다는 것을 이용.
• Topological Sort를 사용한다.

1. 임의의 정점에서 DFS를 수행

• DFS가 끝나는 순서대로 스택에 삽입
• DFS가 끝나고 방문하지 않은 노드가
  있다면 반복

2. 스택의 pop 순서대로 Reverse Graph에서 DFS

• 이때 탐색되는 정점은 SCC요소에 추가
• 스택 empty까지 반복
• 이미 방문된 노드면 pop

타잔 알고리즘