강한 연결 요소, Strongly Connected Component

SCC, 강한 연결 요소(Strongly Connected Componet)

방향이 존재하는 유향 그래프에서 서로 강하게 연결된 부분 집합을 의미, 강하게 연결되있다 -> 사이클이 형성된다.

설명보다 아래 그림을 보면 쉽게 이해된다. 각각의 영역이 SSC를 이룬다.

 

코사라주 알고리즘(Kosaraju's Algorithm)

1. 입력된 그래프에 대해 역방향 그래프를 만듬

2. 그래프에 대해서 DFS를 수행하고, 끝나는 순서대로 스택에 push

3. 스택을 하나씩 pop하면서 역방향 그래프에서 DFS를 수행

- 이미 방문한 정점의 경우 pop만 수행

- 방문하지 않은 정점에 대해 DFS를 수행하고, 이 때 탐색되는 정점들이 하나의 SCC

 

동작 방식

0.  Input, 그래프와 역방향 그래프를 생성해준다.

# Input
7 9 # 정점, 간선개수
1 4
4 5
5 1
1 6
6 7
2 7
7 3
3 7
7 2

입력 그래프

역방향 그래프

 

1. DFS 탐색

DFS 탐색을 돌리며, 탐색이 끝난다면 스택에 정점들을 추가해 준다.

스택의 상태는 5 - 4 - 3 - 2 - 7 - 6 - 1 과 같다.

DFS 후 스택 값

 

2. 스택을 하나씩 POP하면서 역방향그래프에서 DFS를 수행한다.

- 1번 정점에 대해 DFS 수행 (1, 5, 4)

 

- 6번 정점에 대해 DFS 수행, 1번은 이미 방문되었기 때문에 더 이상 방문하지 않는다. (6)

 

- 7번 정점에 대해 DFS 수행, (7, 2, 3)

 

- 나머지 정점들에 대해서도 계속 진행하지만, 5, 4, 3, 2는 이미 방문되었기 때문에 따로 SCC가 생기지 않는다.

 

문제

강한연결요소(기본): https://www.acmicpc.net/problem/2150

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <string>
using namespace std;
vector<int> graph[10001];
vector<int> rev[10001];
int N, M;
stack<int> s;
int visited[10001];
int visited2[10001];
vector<vector<int>> ans;
struct zip {
    int k, v;
    bool operator<(zip o) const {
        return v < o.v;
    }
};
vector<zip> result;
void dfs(int nxt)
{
    for (int i = 0; i < graph[nxt].size(); ++i) {
        int curr = graph[nxt][i];
        if (visited[curr]) continue;
        visited[curr] = 1;
        dfs(curr);
    }
    s.push(nxt);
}
void dfs2(int nxt, int idx)
{
    for (int i = 0; i < rev[nxt].size(); ++i) {
        int curr = rev[nxt][i];
        if (visited2[curr]) continue;
        visited2[curr] = 1;
        dfs2(curr, idx);
    }
    ans[idx].push_back(nxt);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    int a, b;
    for (int i = 0; i < M; ++i)
    {
        cin >> a >> b;
        graph[a].push_back(b);
        rev[b].push_back(a);
    }
    for (int i = 1; i <= N; ++i) {
        if (visited[i]) continue;
        visited[i] = 1;
        dfs(i);
    }

    //while (!s.empty()) { cout << s.top() << " "; s.pop(); }

    int idx = 0;
    while (!s.empty())
    {
        int curr = s.top();
        s.pop();
        if (visited2[curr]) continue;
        visited2[curr] = 1;
        ans.push_back(vector<int>());
        dfs2(curr, idx);
        idx++;
    }

    for (int i = 0; i < idx; ++i) {
        sort(ans[i].begin(), ans[i].end());
    }

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

    cout << result.size() << "\n";
    for (int i = 0; i < result.size(); ++i) {
        int index = result[i].k;
        for (int j = 0; j < ans[index].size(); ++j) {
            cout << ans[index][j] << " ";
        }
        cout << "-1\n";
    }
    return 0;
}