본문 바로가기

알고리즘 관련/BOJ

BOJ)2150 Strongly Connected Component

문제: icpc.me/2150


SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다.


코사라주 알고리즘을 통하여 구현하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstring>
#define MAX_V 10000
using namespace std;
int v, e, visited[MAX_V + 1], x, y, r;
vector<vector<int>> scc;
vector<vector<int>> vt;
vector<vector<int>> rvt;
stack<int> st;
bool cmp(vector<int> x, vector<int> y) {
    return x[0< y[0];
}
void dfs(int v) {
    visited[v] = true;
    for (int next : vt[v]) {
        if (visited[next])
            continue;
        dfs(next);
    }
    st.push(v);
}
void func(int v, int c) {
    visited[v] = true;
    scc[c].push_back(v);
    for (int next : rvt[v]) {
        if (visited[next])
            continue;
        func(next, c);
    }
}
int main() {
    scanf("%d%d"&v, &e);
    vt.resize(v + 1);
    rvt.resize(v + 1);
    for (int i = 0; i < e; i++) {
        scanf("%d%d"&x, &y);
        vt[x].push_back(y);
        rvt[y].push_back(x);
    }
    for (int i = 1; i <= v; i++) {
        if (visited[i])
            continue;
        dfs(i);
    }
    memset(visited, 0sizeof(visited));
    while (st.size()) {
        int here = st.top();
        st.pop();
        if (visited[here])
            continue;
        scc.resize(++r);
        func(here, r - 1);
    }
    for (int i = 0; i < r; i++
        sort(scc[i].begin(), scc[i].end());
    sort(scc.begin(), scc.end());
    printf("%d\n", r);
    for (int i = 0; i < r; i++) {
        for (int x : scc[i])
            printf("%d ", x);
        printf("-1\n");
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13711 LCS4  (0) 2017.01.22
BOJ)1183 약속  (0) 2017.01.22
BOJ)3176 도로 네트워크  (0) 2017.01.21
BOJ)11983 Radio Contact  (0) 2017.01.21
BOJ)1766 문제집  (0) 2017.01.20