강결합 컴포넌트란
강연결 요소라고도 불리는 강결합 컴포넌트는 유향 그래프 내에서 정의되는 개념이다. 유향 그래프에서 두 정점 사이에서 양 쪽 모두 이동할 수 있는 경로가 존재하면 두 정점은 같은 강결합 컴포넌트(SCC)에 속해 있다고 말한다. 만약 같은 SCC에 속한 두 정점 중 한 정점이 또 다른 정점과 같은 SCC에 속해 있으면 세 정점간 오고 가는 경로는 당연히 존재하므로 세 정점이 모두 같은 SCC에 속해있게 된다.
SCC는 일방 통행 도로들로 이뤄진 도시의 도로망 등 그래프를 응용하는 분야에서 자주 사용되는 개념이다.
타잔 알고리즘이란
주어진 그래프를 SCC로 분할하는 알고리즘이다. 타잔 알고리즘은 한번의 dfs로 각 정점을 scc로 분할한다.
dfs 스패닝 트리에서 scc를 분할하는 방법은 특정 정점을 기준으로 그 정점의 앞에 있는 간선을 자르기만 하면 된다. 자를 정점 뒤에 있는 정점이 자를 정점보다 앞에 있는, 즉 먼저 온 정점과 같은 scc로 묶일 가능성은 없다. 이 것은 그림을 그려 생각해보면 쉽게 이해할 수 있다.
그럼 어떤 정점 앞에서 잘라야 scc를 얻을 수 있을 지를 결정하면 된다. 잘리는 정점은 반드시 그 정점을 포함한 scc 트리의 루트가 되는 정점이다. 즉 해당 정점을 기준으로 그 정점의 아래에 있는 정점들은 그 정점 사이에 있는 정점들끼리 자유롭게 오고 갈 수 있지만 그 정점 위에 있는 정점으로 이동하는 것은 불가능한 구조인 것이다.
잘 생각해 보면 이 특성은 절단점의 특성과 매우 유사하다. 따라서 절단점을 구하는 알고리즘을 활용하면 이를 쉽게 해결할 수 있다.
scc를 만드는 루트 정점을 제거했을 때 절단점이 된다면, 그 정점을 기준으로 그 정점보다 선조에 있는 정점을 가는 방법은 전혀 없는 것이고, 따라서 scc의 조건을 만족한다.
주의점으로는 절단점 알고리즘은 무향 그래프를 가정한 알고리즘이기 때문에 교차 간선에 대한 고려가 없다. 따라서 scc를 구분하는 알고리즘을 만들 때에는 교차 간선을 선조로 향하는 간선으로 착각하는 일이 없어야 하기 때문에 교차 간선과 역방향 간선을 구별하는 조건문이 필요하다.
타잔 알고리즘의 구현
타잔 알고리즘의 기본적인 틀은 절단점 알고리즘과 유사하다. 차이점은 역행 간선을 활용할 때 교차 간선과 구분하기 위해서 finished 벡터를 활용 해 dfs가 이미 끝났는 지를 확인하는 부분과, scc가 발견되었을 때 스택 변수를 활용해서 scc로 묶일 정점들을 추출하는 부분이다.
