문제 설명

• 강한 연결 요소의 개수와 그 조합을 출력하는 문제
• 강한 연결 요소란?
  • SSC, 방향이 있는 그래프에서 서로 강하게 연결되어 있는 부분 집합을 의미
  • 강하여 연결되어 있다 = 하나의 사이클이 존재, 즉 하나의 SCC내의 두 정점 u, v는 서로에게 도달 할 수 있는 경로가 직접적/간접적으로 존재

문제 해결 Key_point

• 강한 연결 요소를 구하는 방법
• 타잔 알고리즘
• 코사라주 알고리즘(이번에는 코사라주 알고리즘을 사용해보자)
  • 2번의 dfs를 통해 문제 해결
  • 정방향 그래프, 역방향 그래프, 스택과 방문처리 배열이 필요
• 코사라주 알고리즘 순서
  1. 정방향 그래프 탐색(탐색 중 사이클이 발생한다면, 이전 노드로 복귀하면서 스택에 현재 노드 넣기)
  2. 원점으로 돌아왔으면 다음 방문되지 않은 노드에서 1번 과정 반복
  3. 모두 방문 되었다면, 스택은 완성되어 있음
  4. 이제 visited 배열을 초기화함 (전체 방문되지 않은 false 상태)
  5. 다음으로 역방향 그래프를 스택 기준으로 탐색
  6. 스택에서 뺄 수 있는 순서 그대로 dfs 실행
  7. 사이클이 있다면 그 사이클이 있는 것들끼리 강현 연결 요소임

문제 해결 아이디어

• SSC를 구하는 방법인 코사라주 알고리즘을 사용
• DFS 탐색 함수를 2가지 정의
• 하나는 정방향 하나는 역방향 그래프 탐색을 위한 것
• 정향향 그래프로 탐색하여 스택을 채운 후, 역방향 탐색을 하여 SSC를 채움
• SSC를 오름차순 정렬하여, 출력하면 끝!

소스 코드

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

using namespace std;

int vertex_num, edge_num;
vector<vector<int>> graph, rev_graph;
vector<bool> visited;
stack<int> stack1;
vector<vector<int>> scc;

void dfs1(int node) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) dfs1(next);
    }
    stack1.push(node);
}

void dfs2(int node, vector<int>& component) {
    visited[node] = true;
    component.push_back(node);
    for (int next : rev_graph[node]) {
        if (!visited[next]) dfs2(next, component);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> vertex_num >> edge_num;
    graph.resize(vertex_num + 1);
    rev_graph.resize(vertex_num + 1);
    visited.resize(vertex_num + 1, false);

    for (int i = 0; i < edge_num; i++) {
        int start, end;
        cin >> start >> end;
        graph[start].push_back(end);
        rev_graph[end].push_back(start);
    }

    for (int i = 1; i <= vertex_num; i++) {
        if (!visited[i]) dfs1(i);
    }

    for (int i = 1; i <= vertex_num; i++) {
        visited[i] = false;
    }

    while (!stack1.empty()) {
        int node = stack1.top();
        stack1.pop();
        if (!visited[node]) {
            vector<int> component;
            dfs2(node, component);
            sort(component.begin(), component.end());
            scc.push_back(component);
        }
    }

    sort(scc.begin(), scc.end());

    cout << scc.size() << '\n';
    for (auto& comp : scc) {
        for (int node : comp) {
            cout << node << ' ';
        }
        cout << "-1\n";
    }

    return 0;
}

소감

어렵다… 예시 코드를 보고 겨우 풀었다. 개념은 간단했지만, dfs를 너무 오랜만에 해서 까먹었다. 해당 개념의 대른 문제를 더 풀어봐야겠다.