(3977) 축구 전술

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

단계별로 풀어보기

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

 

 

 

도미노 문제처럼 생각하면 모든 구역에 도달 가능한 시작 구역은 모든 도미노를 쓰러트릴 수 있는 시작 도미노와 마찬가지다. 따라서 SCC 단위로 진입 차수를 구한 뒤 진입 차수가 0인 SCC가 두 개 이상 있다면 Confused를 출력하고, 하나라면 모든 노드를 탐색해 진입 차수가 0인 SCC의 id를 갖고 있다면 출력하면 된다.

 

 

 

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

void solve(){
  int n, m, cnt= 1, idx= 1, anssccidx= 0;
  
  cin >> n >> m;
  
  vector<int> check(n), scc(n);
  vector adj(n, vector<int> ());
  stack<int> s;
  
  while(m--){
    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(!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=0;i<n;i++){
    if(check[i])  continue;
    
    dfs(dfs, i);
  }
  
  vector<int> indegree(idx);
  for(int i=0;i<n;i++){
    for(int j:adj[i]){
      if(scc[i]!=scc[j]){
        indegree[scc[j]]++;
      }
    }
  }
  
  for(int i=1;i<idx;i++){
    if(!indegree[i]){
      if(!anssccidx){
        anssccidx= i;
      }else{
        cout << "Confused\n\n";
        
        return;
      }
    }
  }
  
  for(int i=0;i<n;i++){
    if(scc[i]==anssccidx)  cout << i << "\n";
  }
  cout << "\n";
}

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