백준[2150] Strongly Connected Compoment

문제 설명

문제 링크

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

풀이

이 문제는 SCC를 구하는 문제이다. 나는 코사라주 알고리즘(Kosaraju's algorithm)을 이용하여 SCC를 구했다.

코사라주 알고리즘은 우선 방향 그래프와 역방향 그래프를 dfs로 탐색하며 진행된다.

1. 방향 그래프를 dfs로 탐색하며 더 이상 갈 수 있는 곳이 없을 때 stack에 push 한다.

    -이 과정을 모든 정점에 대해 dfs를 진행할 때까지 반복한다.

2. 역방향 그래프를 stack의 top부터 순회하며 이때 만나는 노드들이 SCC다.

    -이때 top에 있는 정점이 이미 방문한 정점이라면 pop을 한다.

https://stonejjun.tistory.com/113 증명은 이 글을 참고하자.

코드

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>

using namespace std;

vector<int> v[10004];
vector<int> rev[10004];
vector<int> ans[10004];
stack<int> s;
bool visited[10004];
int sz;

bool compare(vector<int> a, vector<int> b) {
    return a[0] < b[0];
}

void dfs(int cur) {
    visited[cur] = true;
    for (auto nxt : v[cur]) {
        if (!visited[nxt]) dfs(nxt);
    }
    s.push(cur);
}

void rev_dfs(int cur) {
    visited[cur] = true;
    ans[sz].push_back(cur);
    for (auto nxt : rev[cur]) {
        if (!visited[nxt]) rev_dfs(nxt);
    }
}

int main() {
    int V, E; scanf("%d %d", &V, &E);
    for (int i = 0; i < E; i++) {
        int a, b; scanf("%d %d", &a, &b);
        v[a].push_back(b);
        rev[b].push_back(a);
    }
    for (int i = 1; i <= V; i++) {
        if (!visited[i]) dfs(i);
    }
    memset(visited, 0, sizeof visited);
    while (!s.empty()) {
        int cur = s.top();
        s.pop();
        if (visited[cur]) continue;
        rev_dfs(cur);
        sz++;
    }

    printf("%d\n", sz);

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

    for (int i = 0; i < sz; i++) {
        for (auto k : ans[i]) {
            printf("%d ", k);
        }
        printf("-1\n");
    }
}

참고

https://wondy1128.tistory.com/130

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