[백준 3977] 축구 전술 C++

3977번: 축구 전술

강한 연결 요소

---

1. 문제 해결 아이디어

 

도미노 문제와 매우 비슷한 문제이다.

 

<다른 모든 구역에 도달할 수 있는 시작 구역을 찾은 뒤 지시한 움직임만을 따라가라고 했다.> 이 문장을 통해서 SCC임을 알 수 있다.

 

 

강한 연결 요소 (SCC) - 타잔 알고리즘

 

위 글에서 설명한 타잔 알고리즘을 통해서 문제를 해결했다.

각각의 정점들을 특정한 SCCID를 가진 그룹으로 나눌 수 있고, 나눠진 그룹들은 서로 연결될 수도 있고, 아닐수도 있다.

 

SCC가 indegree(들어오는 간선)을 가지고 있다면 시작 지점이 될 수 없다.

SCC간의 연결은 양방향 연결이 될 수 없기 때문에(양방향 연결이 된다면 이미 같은 SCC에 포함됨) SCC가 indegree를 가지고 있다면 해당 SCC에서 출발해서는 절대로 모든 SCC를 탐색할 수 없다.

 

따라서 indegree가 0인 SCC가 2개 이상이라면 (indegree가 0인 SCC들도 서로를 탐색할 수 없기 때문에) 답을 구할 수 없다. (indegree가 0인 SCC가 하나도 없을수는 없다.

 

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
vector< vector<int> > adj;
int discovered[100001];
int SCCID[100001];
int sccindegree[100001];
int Vcnt;
int SCCcnt;
 
void init(){
    cin >> N >> M;
    
    memset(discovered, -1, sizeof(discovered));
    memset(SCCID, -1, sizeof(SCCID));
    memset(sccindegree, 0, sizeof(sccindegree));
    adj.clear();
    adj.resize(N+1, vector<int>());
    Vcnt = SCCcnt = 0;
    
    int u, v;
    for(int i = 0; i < M; i++){
        cin >> u >> v;
        adj[u].push_back(v);
    }
}
 
vector<int> stk;
 
int findSCC(int now){
    int ret = discovered[now] = Vcnt++;
    stk.push_back(now);
    
    for(auto &next : adj[now]){
        if(discovered[next] == -1){
            ret = min(ret, findSCC(next));
        }
        else if(SCCID[next] == -1){
            ret = min(ret, discovered[next]);
        }
    }
    
    if(discovered[now] == ret){
        while(true){
            int temp = stk.back();
            stk.pop_back();
            SCCID[temp] = SCCcnt;
            if(temp == now) break;
        }
        SCCcnt++;
    }
    
    return ret;
}
 
void solve(){
    for(int i = 0; i < N; i++){
        if(discovered[i] != -1) continue;
        findSCC(i);
    }
    
    for(int i = 0; i < N; i++){
        for(auto &w : adj[i]){
            if(SCCID[w] == SCCID[i]) continue;
            sccindegree[SCCID[w]]++;
        }
    }
    
    vector<int> temp;
    for(int i = 0; i < SCCcnt; i++){
        if(!sccindegree[i]){
            temp.push_back(i);
        }
    }
    if(temp.size() > 1 || temp.empty()){
        cout << "Confused\n";
    }
    else{
        for(int i = 0; i < N; i++){
            if(SCCID[i] == temp[0]){
                cout << i << "\n";
            }
        }
    }
    cout << "\n";
}
 
int main(){
    fasti
    int test;
    cin >> test;
    while(test--){
        init();
        solve();    
    }
    
    return 0;
}