[2150번] Strongly Connected Component

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. SCC :: http://www.crocus.co.kr/950

SCC를 알면 풀 수 있는 기본이 되는 문제이다.

여기서 SCC이외에 요구사항은 정렬을 해서 출력하고 출력의 끝에 -1을 붙여 출력해달라는 것 이외에는 다른 요구사항은 없다.

위의 링크에서 SCC를 공부하고 문제를 풀어보면 될 것 같다.

소스 코드 : 

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
const int MAX = 10010;
 
// SCCtotal : SCC 개수, sn[i]: i가 속한 SCC의 번호
int V, E, cnt, dfsn[MAX], SCCtotal, sn[MAX];
vector<int> adj[MAX];
bool finished[MAX]; // SCC가 확정된 정점 판별
stack<int> s;
vector<vector<int>> SCC;
 
// SCC에 사용될 dfs
int dfs(int curr)
{
    dfsn[curr] = ++cnt; // dfsn 결정
    s.push(curr); // 스택에 자신을 push
 
    // 자신의 dfsn, 자식들의 결과나 dfsn 중 가장 작은 번호를 result에 저장
    int result = dfsn[curr];
    for (int next : adj[curr])
    {
        // 아직 방문하지 않은 이웃
        if (dfsn[next] == 0)
            result = min(result, dfs(next));
 
        // 방문은 했으나 아직 SCC로 추출되지는 않은 이웃
        else if (!finished[next])
            result = min(result, dfsn[next]);
    }
 
    // 자신, 자신의 자손들이 도달 가능한 제일 높은 정점이 자신일 경우 SCC 추출
    if (result == dfsn[curr])
    {
        vector<int> curSCC;
        // 스택에서 자신이 나올 때까지 pop
        while (1)
        {
            int t = s.top();
            s.pop();
            curSCC.push_back(t);
            finished[t] = true;
            sn[t] = SCCtotal;
 
            if (t == curr)
                break;
        }
 
        // 출력을 위해 원소 정렬
        sort(curSCC.begin(), curSCC.end());
 
        // SCC에 현재 이루어진 SCC 정보 push_back
        SCC.push_back(curSCC);
        SCCtotal++; // SCC 개수 
    }
 
    return result;
}
 
int main() {
    // 그래프 정보 입력
    scanf("%d %d", &V, &E);
    for (int i = 0; i< E; i++) {
        int from, to;
        scanf("%d %d", &from, &to);
        adj[from].push_back(to);
    }
 
    // DFS를 하며 SCC 추출
    for (int i = 1; i <= V; i++)
        if (dfsn[i] == 0)
            dfs(i);
 
    // 출력을 위해 SCC들을 정렬
    sort(SCC.begin(), SCC.end());
 
    // SCC 개수
    printf("%d\n", SCCtotal);
 
    // 각 SCC 출력
    for (auto& currSCC : SCC)
    {
        for (int curr : currSCC)
            printf("%d ", curr);
 
        printf("-1\n");
    }
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>