(4196) 도미노

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

단계별로 풀어보기

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

 

 

 

같은 SCC 내 도미노는 무엇을 쓰러트리든 전부 쓰러지기 때문에 하나의 도미노라고 생각할 수 있다.

따라서 SCC 집합끼리의 도미노라고 생각하고 문제를 풀어도 된다. 어떤 도미노가 손으로 넘어트려야 한다는 것은, 이 도미노를 쓰러트리는 도미노가 없다는 것이다. 다시 말해 각 SCC 도미노의 진입 차수를 구해 0인 도미노의 수가 정답이 된다.

타잔 알고리즘으로 모든 도미노에 SCC 기준으로 구별되는 id를 붙인 뒤, 간선을 다시 전부 순회하며 id가 다른 간선이 있다면 도착 노드의 id에 진입 차수를 1 증가시킨다. 마지막으로 SCC의 수만큼 순회하며 진입 차수가 0인 수를 구하면 된다.

 

 

 

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

int solve(){
  int n, m, cnt= 1, idx= 1, ans= 0;
  
  cin >> n >> m;
  
  vector<int> check(n+1), scc(n+1);
  vector adj(n+1, vector<int> ());
  stack<int> s;
  
  while(m--){
    int x, y;
    
    cin >> x >> y;
    
    adj[x].push_back(y);
  }
  
  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(!scc[next]){
        low= min(low, check[next]);
      }
    }
    
    if(check[now]==low){
      while(true){
        int here= s.top();
        s.pop();
        scc[here]= idx;
        
        if(here==now)  break;
      }
      
      idx++;
    }
    
    return low;
  };
  
  for(int i=1;i<=n;i++){
    if(check[i])  continue;
    
    dfs(dfs, i);
  }
  
  vector<int> indegree(idx);
  for(int i=1;i<=n;i++){
    for(int j:adj[i]){
      if(scc[i]!=scc[j]){
        indegree[scc[j]]++;
      }
    }
  }
  
  for(int i=1;i<idx;i++){
    ans+= !indegree[i];
  }
  
  return ans;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}

 

 

 

사실 더 간단한 풀이가 있는데, 코사라주 알고리즘처럼 DFS를 돌렸을 때 스택 가장 위에 쌓인 노드는 출발점에 가장 가까운 노드라는 특성을 이용하면 된다. 간선을 역방향으로 돌리지 않고 스택에서 꺼내 DFS를 돌리면 해당 SCC 및 간선으로 연결된 다른 SCC를 전부 방문하게 된다. 따라서 스택에서 꺼내는 순서대로 노드를 확인했을 때 방문한 적이 없다면 SCC로 이루어진 DAG에서 진입 차수가 0이라는 의미고, 이 노드(SCC) 도미노를 쓰러트려야 한다는 의미가 된다. 정답 값을 1 증가시키고 해당 노드로 DFS를 돌리면 된다.

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

int solve(){
  int n, m, ans= 0;
  
  cin >> n >> m;
  
  vector<bool> visited(n+1);
  vector adj(n+1, vector<int> ());
  stack<int> s;
  
  while(m--){
    int x, y;
    
    cin >> x >> y;
    
    adj[x].push_back(y);
  }
  
  auto dfs= [&](auto self, int now, bool type= true) -> void {
    visited[now]= true;
    
    for(int next:adj[now]){
      if(visited[next])  continue;
      
      self(self, next);
    }
    
    if(type)  s.push(now);
  };
  
  for(int i=1;i<=n;i++){
    if(visited[i])  continue;
    
    dfs(dfs, i);
  }
  
  visited= vector<bool> (n+1);
  
  while(!s.empty()){
    int now= s.top();
    s.pop();
    
    if(visited[now])  continue;
    
    ans++;
    dfs(dfs, now, false);
  }
  
  return ans;
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }
  
  return 0;
}