[백준] No.2150 - Strongly Connected Component (C++, 강결합 컴포넌트, 타잔 알고리즘)

문제

 

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

 

풀이

 

solved.ac 난이도: Platium 5

 

강결합 컴포넌트(Strongly Connected Component)는 방향 그래프에서만 정의된다.

그래프에서 두 정점에 대해서 양방향으로 이동 가능한 경로가 모두 있을 때 두 정점은 같은 강결합 컴포넌트(SCC)에 속한다.

즉, 그래프의 사이클에서 같은 사이클 내에 존재하는 정점들은 같은 SCC에 속한다 할 수 있다.

 

다음 그림은 그래프에서 같은 SCC끼리를 사각형으로 묶어 나타냈다.

 

주어진 그래프에서 같은 SCC를 묶어내기 위해 사용하는 알고리즘이 타잔(Tarjan) 알고리즘이다.

타잔 알고리즘을 공부하기 전에 비슷한 방법으로 해결하는 무향 그래프의 절단점과 절단선을 먼저 공부하고 오면 이해가 더 잘 될것이다.

 

 

타잔(Tarjan) 알고리즘

 

 타잔 알고리즘은 깊이 우선 탐색으로 방향 그래프의 정점들을 방문하는데, 방문한 정점의 간선을 통해 상위에서 방문된 정점을 방문할 다면 사이클, SCC가 존재함을 알 수 있다. 단, 사이클의 존재 여부만 파악하는 것이 아닌 같은 SCC를 파악하여 해당 SCC의 정점 중 가장 작은 정점의 번호를 출력해야 한다. 따라서 같은 SCC에 속하는 정점들은 vector배열(sccs)에 저장하여 정답을 구하자.

 

 

vector<vector<int>> adj;
stack<int> st;
vector<int> visited_order;
vector<bool> is_scc;
vector<vector<int>> sccs;
int order=0;
 
int FindSCC(int now_idx){
  int min_order = visited_order[now_idx] = ++order;
  int next_idx;
  st.push(now_idx);
 
  for(int i=0 ; i<adj[now_idx].size() ; ++i){
    next_idx = adj[now_idx][i];
    if(visited_order[next_idx] == -1)
      min_order = min(min_order, FindSCC(next_idx));
    else if(!is_scc[next_idx])
      min_order = min(min_order, visited_order[next_idx]);
  } 
    //DFS 재귀 방문을 마친 후에 간선을 끊을지 검사
  if(min_order == visited_order[now_idx]){
    int temp;
    vector<int> new_scc;
    while(1){
      temp = st.top();
      st.pop();
      is_scc[temp] = true;
      new_scc.push_back(temp);
      if(temp == now_idx)
        break;
    }
 
    sccs.push_back(new_scc);
  }
  return min_order;
}

 

FindSCC는 현재의 정점(now_idx)의 방문 순서(visited_order)를 저장하고 이를 스택에 저장한다.

그 후에 현재의 정점(now_idx)과 인접한 정점(adj에 저장)을 확인하기 때문에 하위 정점들은 항상 now_idx보다 스택에 늦게 삽입된다.

 

이제 간선으로 이어진 정점들을 순회하며 결정된 SCC는 SCC의 루트 노드(SCC 중에서 처음으로 방문된 정점)의 부모와 SCC 연결을 작업을 해주어야 한다.

이 작업을 위해서 FindSCC 함수가 종료되는 시점에서 현재 정점 now_idx가 SCC의 루트 노드인지의 여부를 확인한다.

이를 위해 now_idx에서 갈 수 있는 가장 빨리 방문된 정점(min_order)을 구해야 한다.

만약 min_order가 now_idx의 방문 순서와 같다면 now_idx는 SCC의 루트 노드에 해당하므로 부모와 다른 SCC를 구성한다.

 

now_idx에 인접한, 다음으로 방문할 정점(next_idx)이 이미 방문된 정점이라면(visited_order[next_idx] != -1의 경우)

now_idx와 사이클을 이룰 수도 있지만, 그전에 해당 정점이 이미 다른 SCC에 속하는 지를 확인해야 한다.

그 이유는 무향 그래프와 달리 방향 그래프에는 역방향으로 가는 간선이 존재하지 않을 수 있기 때문이다.

 

예를 들어 다음과 같은 그래프를 확인해보자.

 

 

1번 정점부터 DFS 방문을 시작한다면

1번 방문 -> 2번 호출 /  호출 스택: 1   / 정점 저장 스택: 1

2번 방문 -> 3번 호출 /  호출 스택: 1 2  / 정점 저장 스택: 1 2

3번 방문 -> 2번 호출(이미 방문) /  호출 스택: 1 2 3  / 정점 저장 스택: 1 2 3

3번 종료 -> 2번 복귀  /  호출 스택: 1 2  / 정점 저장 스택: 1 2 3

2번 종료 -> 1번 복귀 -> 4번 호출  /  호출 스택: 1   / 정점 저장 스택: 1 2 3

4번 방문 -> 5번 호출  /  호출 스택: 1 4   / 정점 저장 스택: 1 2 3 4

5번 방문 -> 3번 호출(이미 방문) / 호출 스택: 1 4 5   / 정점 저장 스택: 1 2 3 4 5

4번 복귀 ->... -> 1번 복귀 / 호출 스택: 1  / 정점 저장 스택: 1 2 3 4 5

1번은 min_order과 자신의 방문 order가 동일하므로 SCC의 루트가 되어 방문한 하위 정점들과 SCC를 이룬다.

이때 스택에 담긴 정점을 자신의 정점 번호가 나올 때까지 빼내 주면 해당 정점들은 모두 같은 SCC에 속한다.

 

하지만 위의 그래프에서 2번 정점에서 1번 정점으로의 간선이 제거된다면

5번 정점이 3번 정점을 방문할 때 이미 3번 정점은 2번 정점과 SCC를 이룬 후일 것이다.

 

따라서 1번 정점으로 이동할 수 없고 3번과 5번 정점은 서로 다른 SCC에 속하게 된다.

즉, 이미 방문한 정점이 SCC를 이루었는가의 여부로 해당 정점과의 SCC관계를 알 수 있다.

 

+SCC구현을 위한 또 다른 알고리즘으로 코사라주 알고리즘도 존재한다.

 

참고 서적: 알고리즘 문제 해결 전략(구종만 저)

 

 

코드