(2150) Strongly Connected Component

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

단계별로 풀어보기

48단계(강한 연결 요소) 1번째

 

 

 

강한 연결 요소(SCC)란 방향 그래프에서 강하게 연결된 부분집합을 의미한다. 여기서 강하게 연결되었다는 것은 사이클이 형성되었다는 것으로, 강한 연결 집합 내 정점 u, v에 대해 서로에게 도달할 수 있는 경로가 항상 존재한다. 무방향 그래프는 그래프 전체가 하나의 SCC라고 볼 수 있어 정의는 가능하지만 의미는 없다.

 

SCC를 구하는 알고리즘은 크게 코사라주 알고리즘과 타잔 알고리즘으로 나뉘는데, 시간 복잡도는 둘 다 O(V+E)로 동일하지만 코사라주 알고리즘이 개념이나 더 구현이 쉬운 대신 간선을 두 배로 관리해야 해서 메모리를 더 쓰고 DFS를 2번 써야 하는 반면 타잔 알고리즘은 DFS를 한 번만 써서 실질적인 속도는 더 빠르고 효율적이라는 장점이 있다. 그래서 일반적으로는 타잔 알고리즘이 많이 쓰인다.

 

코사라주 알고리즘의 원리는 이렇다. DFS를 돌려 모든 노드를 탐색하고, DFS가 끝날 때 해당 노드를 스택에 삽입한다. 여기서 스택의 가장 위에 쌓인 노드는 다른 SCC로 진입하는, 출발점에 가장 가까운 노드라는 것이 수학적으로 증명되어 있다.

이후 간선의 방향을 전부 뒤집는다. SCC 내부의 노드끼리는 사이클을 이루고 있으므로 뒤집어도 영향이 없는 반면, SCC끼리 연결하던 일방통행 길은 방향이 반대가 된다. 따라서 첫 DFS에서 출발점(Source)이었던 노드는 도착점(Sink)으로 바뀌게 된다. 따라서 스택에서 꺼낸 노드에서 DFS를 돌리면 다른 SCC로 가는 길이 없으므로 스스로의 SSC 내부에서만 DFS를 순회하게 된다. 이 SCC를 분리하면(방문 체크) 다음 노드도 스스로의 SCC에서만 DFS를 순회하게 되고, 이 과정을 반복하면 SSC끼리 분류할 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int v, e;
  
  cin >> v >> e;
  
  vector<bool> check(v+1);
  vector<vector<int>> adj(v+1), radj(v+1), scc;
  stack<int> s;
  
  while(e--){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    radj[b].push_back(a);
  }
  
  auto dfs_traversal= [&](auto self, int now) -> void {
    check[now]= true;
    
    for(int next:adj[now]){
      if(check[next])  continue;
      
      self(self, next);
    }
    
    s.push(now);
  };
  
  auto dfs_scc= [&](auto self, int now) -> void {
    check[now]= false;
    scc.back().push_back(now);
    
    for(int next:radj[now]){
      if(!check[next])  continue;
      
      self(self, next);
    }
  };
  
  for(int i=1;i<=v;i++){
    if(check[i])  continue;
    
    dfs_traversal(dfs_traversal, i);
  }
  
  while(!s.empty()){
    int now= s.top();
    s.pop();
    
    if(!check[now])  continue;
    
    scc.push_back(vector<int> ());
    dfs_scc(dfs_scc, now);
  }
  
  for(auto& elem:scc)  sort(elem.begin(), elem.end());
  sort(scc.begin(), scc.end(), [](auto A, auto B){
    return A[0]<B[0];
  });
  
  cout << scc.size() << "\n";
  for(auto& x:scc){
    for(int y:x)  cout << y << " ";
    cout << "-1\n";
  }
  
  return 0;
}

 

 

 

타잔 알고리즘의 원리는 이렇다. DFS를 돌며 방문한 모든 노드에 고유한 방문 순서 번호를 부여한다. 그리고 노드를 스택에 넣는다. 그리고 노드마다 자신이 이동 가능한 가장 작은 번호의 노드인 low를 관리한다. 만약 DFS가 끝날 때 low값이 자신의 방문 순서 번호와 같다면 이 노드나 자식 노드로 더 먼저 방문한 노드에 진입할 수 없다는 의미이므로, 현재 노드가 사이클의 꼭대기라는 것이다. 따라서 스택에서 자기 자신이 나올 때까지 노드를 전부 뽑으며, 이때 뽑힌 노드가 하나의 SCC를 이루게 된다.

참고로 타잔 알고리즘을 통해 만들어지는 SCC의 순서는, SCC들로 이루어진 방향 그래프를 위상 정렬한 순서의 역순이다.

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int v, e, cnt= 1;
  
  cin >> v >> e;
  
  vector<bool> isscc(v+1);
  vector<int> check(v+1);
  vector<vector<int>> adj(v+1), scc;
  stack<int> s;
  
  while(e--){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
  }
  
  auto dfs= [&](auto self, int now) -> int {
    s.push(now);
    check[now]= cnt++;
    int low= check[now];
    
    for(int next:adj[now]){
      if(!check[next]){
        low= min(low, self(self, next));
      }else if(!isscc[next]){
        low= min(low, check[next]);
      }
    }
    
    if(check[now]==low){
      vector<int> tmp;
      
      while(true){
        int here= s.top();
        s.pop();
        isscc[here]= true;
        tmp.push_back(here);
        
        if(here==now)  break;
      }
      
      sort(tmp.begin(), tmp.end());
      scc.push_back(tmp);
    }
    
    return low;
  };
  
  for(int i=1;i<=v;i++){
    if(check[i])  continue;
    
    dfs(dfs, i);
  }
  
  sort(scc.begin(), scc.end(), [](auto A, auto B){
    return A[0]<B[0];
  });
  
  cout << scc.size() << "\n";
  for(auto& x:scc){
    for(int y:x)  cout << y << " ";
    cout << "-1\n";
  }
  
  return 0;
}