[알고리즘] 강한 연결 요소(Strongly Connected Component)

강한 연결 요소(Strongly Connected Component, SCC)는 어떤 양방향 그래프 내에서 다음 조건을 만족하는 부분집합이다.

1. 임의의 강한 연결 요소 내부의 모든 정점끼리는 서로 이어진 경로가 존재한다.
2. 임의의 강한 연결 요소 내부의 정점과 외부의 정점끼리는 서로 이어진 경로가 존재하지 않는다.
   

즉 이는 어떤 한 정점에 대해 첫번째 조건을 만족하는 최대의 부분집합이라고 할 수 있다.

 

위 그래프에서 {A, B, C, E}, {D, G, H}, {F}, {I}가 강한 연결 요소이다.

어떤 그래프에서의 SCC를 찾는 알고리즘으로는 코사라주 알고리즘이 있다.

---

코사라주 알고리즘 |

코사라주 알고리즘은 DFS를 이용한 위상 정렬을 토대로 SCC를 찾는 알고리즘이다.

1. 그래프와 역방향 그래프를 준비한다.
2. 그래프에서 모든 미방문 정점에 대해 DFS를 수행한다.
3. DFS가 먼저 끝나는 순서대로 스택에 넣는다.
4. 스택에서 정점을 뽑아 그 정점에서부터 역방향 그래프에 DFS를 수행한다.
5. 4에서 순회한 정점들의 집합이 SCC이다.

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

using namespace std;

int V, E;
vector<int> graph[10001], reverseGraph[10001];
int SCC[10001];
bool visited[10001], reverseVisited[10001];
stack<int> s;

void DFS(int vertex)
{
    if (visited[vertex])
        return;
    visited[vertex] = true;
    for (int i = 0; i < graph[vertex].size(); i++)
    {
        DFS(graph[vertex][i]);
    }
    s.push(vertex);
    return;
}

void reverseDFS(int vertex, int index)
{
    if (reverseVisited[vertex])
        return;
    reverseVisited[vertex] = true;
    SCC[vertex] = index;
    for (int i = 0; i < reverseGraph[vertex].size(); i++)
    {
        reverseDFS(reverseGraph[vertex][i], index);
    }
    return;
}

int main()
{
    cin >> V >> E;
    for (int i = 0; i < E; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        reverseGraph[b].push_back(a);
    }
    for (int i = 1; i <= V; i++)
        DFS(i);
    int index = 0;
    while (!s.empty())
    {
        if (!reverseVisited[s.top()])
        {
            reverseDFS(s.top(), index);
            index++;
        }
        s.pop();
    };
    cout << index << "\n";
    bool indexChecked[100001] = {
        false,
    };
    for (int i = 1; i <= V; i++)
    {
        if (indexChecked[SCC[i]])
            continue;
        indexChecked[SCC[i]] = true;
        for (int j = 1; j <= V; j++)
        {
            if (SCC[i] == SCC[j])
                cout << j << " ";
        }
        cout << "-1\n";
    }
    return 0;
}

---

관련 문제 |

[BOJ] Strongly Connected Component (https://www.acmicpc.net/problem/2150)