[그래프] 강한 연결 요소 (Strongly Connected Component)
백준 https://www.acmicpc.net/problem/14675 문제 풀이를 위해 단절점과 단절선에 대해 찾아보다가, 이를 이해하기 위해 SCC를 공부한 내용을 기록한다.
SCC의 정의
양방향(=무방향) 그래프에서 다음 조건을 만족하는 정점들의 집합을 강결합 컴포넌트(SCC, Strongly Connected Component)라고 한다.
1. 임의의 두 정점 u, v사이의 u → v 경로와, v → u 경로가 항상 존재한다.
2. 1번 조건을 만족하는(SCC에 속하는) 임의의 정점 u와, 외부의 임의의 정점 v 사이에, u → v 경로와, v → u 경로가 동시에 존재하는 경우는 없다.
이해하기 쉽게 그림으로 알아보자.
위 그래프가 있다. 이때 아래와 같은 정점끼리는 위 조건을 다 만족시켜 SCC에 속한다.
1, 4, 5번 정점: 1에서 4로 가는 경로(1 → 4)와, 4에서 1로 가는 경로(4 → 5 → 1)가 다 존재하고(1번 조건 충족), 2번 조건 또한 충족시킨다.
6번 정점: 6에서 6으로 가는 경로(6 → 6)가 존재하고(나의 노드가 출발점이자 도착점이 될 수 있다, 1번 조건 충족), 2번 조건 또한 충족시킨다.
2, 3, 7번 정점: 2에서 7으로 가는 경로(2 → 7)와, 7에서 2로 경로(7 → 2)가 다 존재하고(1번 조건 충족), 2번 조건 또한 충족시킨다.
끝!
끝이다. 그래프에서 SCC 영역을 구하는 방법은 타잔 알고리즘을 통해 할 수 있다. 코사라주 알고리즘도 있지만, 이보다 타잔 알고리즘이 더 활용도가 높어 타잔 알고리즘만 다음 글에서 다뤄보겠다.
