[C++] 3977번 축구 전술 - 그래프 이론, 강한 연결 요소

1. 문제

• 도현이는 경기장을 여러 구역으로 나누고, 어떤 선수가 A->B 움직임을 (A, B)로 표현한다. 다른 모든 구역에 도달할 수 있는 시작구역을 모두 찾자.

<입력>

• - 1 -   테스트 케이스의 개수 \(T(1 \leq T \leq 11)\)
  • - 1 -   구역의 수 N, 지시한 움직임의 수 M \(1 \leq N, M \leq 100,000)\)
  • - M개의 줄 -   움직임 (A, B) \(0 \leq A, B < N)\)

<출력>

• 가능한 모든 시작 구역을 오름차순으로 출력, 만일 그러한 시작 구역이 없으면 Confused 출력

2. 재정의

• 시작하면 모두 연결되는 정점 모두 출력

3. 해결 방법

• SCC 알고리즘으로 구역 나누기
• 연결되는 그룹들을 모두 제거했을 때 남은 그룹의 개수가 1개면 그 그룹의 모든 원소. 0개면 모든 원소. 2개 이상이면 불가능

4. 실수한 점, 개선할 점

• X

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int MAX_N = 100001;

// <문제>
// 테스트 케이스의 개수 T
int T;
// 구역의 수 N, 지시한 움직임의 수 M;
int N, M;
// 움직임을 나타내는 무가중치 방향 그래프 adj
vector<int> adj[MAX_N];

// SCC Tarjan Algorithm
stack<int> st;
int discover[MAX_N], scc[MAX_N];
int sccCnt, sccSize;
vector<int> SCCNode[MAX_N];
bool repreSCC[MAX_N];
int startSCC;

// SCC Tarjan Algorithm
int dfs(int no) {
    st.push(no);
    discover[no] = sccCnt++;
    int parent = discover[no];
    
    for(auto next : adj[no]) {
        if(discover[next] == -1)
            parent = min(parent, dfs(next));
        else if(scc[next] == -1)
            parent = min(parent, discover[next]);
    }
    
    if(parent == discover[no]) {
        while(true) {
            int x = st.top();
            st.pop();
            scc[x] = sccSize;
            SCCNode[sccSize].push_back(x);
            if(no == x)
                break;
        }
        sccSize++;
    }
    
    return parent;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> T;
    while(T--) {
        // <초기화>
        for(int i=0; i<MAX_N; i++) {
            adj[i].clear();
            SCCNode[i].clear();
        }
        memset(discover, -1, sizeof discover);
        memset(scc, -1, sizeof scc);
        sccCnt = sccSize = 1;
        fill(repreSCC, repreSCC+MAX_N, true);
        
        // <input>
        cin >> N >> M;
        for(int i=0; i<M; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
        }
        
        for(int i=0; i<N; i++) {
            // 아직 탐색하지 않은 노드 SCC
            if(discover[i] == -1)
                dfs(i);
        }
        
        // 그룹 지어 자동으로 연결되는 그룹은 pass하기
        for(int i=0; i<N; i++)
            for(auto next : adj[i])
                if(scc[i] != scc[next])
                    repreSCC[scc[next]] = false;
        
        sccSize--;
        int cnt = 0;
        for(int i=1; i<=sccSize; i++) {
            // 다음으로 연결되지 않을 경우 반드시 시작점이 되어야 한다.
            if(repreSCC[i]) {
                cnt++;
                startSCC = i;
            }
        }
        
        if(!cnt) {
            for(int i=0; i<N; i++)
                cout << i << '\n';
        }
        else if(cnt == 1) {
            sort(SCCNode[startSCC].begin(), SCCNode[startSCC].end());
            for(auto x : SCCNode[startSCC]) {
                // 오름차순 정렬
                cout << x << '\n';
            }
        }
        else
            cout << "Confused" << '\n';
        cout << '\n';
    }
    
    return 0;
}

 

<문제 바로가기>

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

3977번: 축구 전술

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.