[백준 2150번] 강한연결요소(Strongly Connected Component)

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

Strongly Connected Component 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2547	1186	650	43.304%

문제

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.

입력

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이 때 방향은 A->B가 된다.

출력

첫째 줄에 SCC의 개수를 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

예제 입력 1 

7 9
1 4
4 5
5 1
1 6
6 7
2 7
7 3
3 7
7 2

예제 출력 1 

3
1 4 5 -1
2 3 7 -1
6 -1

알고리즘 스터디에서 강한연결요소를 공부하면서 해결한 기본 문제이다.

생소한 개념이었는데 참고한 블로그가 매우 설명이 잘 되있어서 쉽게 이해할 수 있었다.

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
 
using namespace std;
 
int V, E, e1, e2, cnt, SCC_num;
int numbering[10001];
int scc_numbering[10001];
vector<int> graph[10001];
vector<vector<int>> SCC;
stack<int> sta;
bool finished[10001];
 
int dfs(int);
 
int main() {
 
    cin >> V >> E;
 
    for (int i = 0; i < E; i++) {
        cin >> e1 >> e2;
        graph[e1].push_back(e2);
    }
 
    for (int i = 0; i < V; i++) {
        if (numbering[i+1] == 0) dfs(i+1);
    }
 
    sort(SCC.begin(), SCC.end());
 
    cout << SCC_num << "\n";
    for (int i = 0; i < SCC.size(); i++) {
        for (int j = 0; j < SCC[i].size();j++) {
            cout << SCC[i][j] << " ";
        }
        cout << "-1\n";
    }
 
    return 0;
}
 
int dfs(int num) {
 
    numbering[num] = ++cnt;
    sta.push(num);
 
    int result = numbering[num];
    for (int i : graph[num]) {
        if (numbering[i] == 0) result = min(result, dfs(i));
        else if (!finished[i]) result = min(result, numbering[i]);
    }
 
    if (result == numbering[num]) {
        vector<int> temp;
        while (1) {
            int t = sta.top();
            sta.pop();
            temp.push_back(t);
            finished[t] = true;
            scc_numbering[t] = SCC_num;
            if (t == num) break;
        }
        sort(temp.begin(), temp.end());
        SCC.push_back(temp);
        SCC_num++;
    }
    return result;
}