백준 2150 (C++) Strongly Connected Component

최초 업로드: 2025-04-21 20:43:47

최근 수정 시간: 2025-07-25 09:24:13

게시자: rlatjwls3333

카테고리: 백준

# [Platinum V] Strongly Connected Component

#### [문제 링크](https://www.acmicpc.net/problem/2150)

## 문제 설명

방향 그래프가 주어졌을 때, 그 그래프를 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가 된다.

정점은 1부터 V까지 번호가 매겨져 있다.

## 출력

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

## 풀이
#### 문제의 설명대로 SCC 알고리즘을 사용하여 풀면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 10001;

bool visited[MAX];
int idx, parent[MAX];
vector<vector<int>> conn(MAX), SCCs;
stack<int> stk;

int dfs(int cur) {
    stk.push(cur);
    int rem = parent[cur] = ++idx;

for(int next:conn[cur]) {
        if(!parent[next]) rem = min(rem, dfs(next));
        else if(!visited[next]) rem = min(rem, parent[next]);
    }

if(rem==parent[cur]) {
 SCCs.push_back(vector<int>());
 while(true) {
 int top = stk.top(); stk.pop();
 SCCs.back().push_back(top);
 visited[top] = true;
 parent[top] = rem;
 if(top==cur) break;
 }
 }
 return rem;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int v, e; cin >> v >> e;

while(e--) {
        int a, b; cin >> a >> b;
        conn[a].push_back(b);
    }

// dfs
 for(int i=1;i<=v;i++) {
 if(!visited[i]) dfs(i);
 }

// sort
 for(int i=0;i<SCCs.size();i++) {
 sort(SCCs[i].begin(), SCCs[i].end());
 }
 sort(SCCs.begin(), SCCs.end());

// print
 cout << SCCs.size() << endl;
 for(auto SCC:SCCs) {
 for(int val:SCC) {
 cout << val << ' ';
 }
 cout << "-1\n";
 }
}
```