[백준] 2150번 - Strongly Connected Component

Strongly Connected Component

문제 링크

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

문제 풀이

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <random>
#include <time.h>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <stack>
#include <deque>
#include <cstring>
#define MAX 26
#define INF 987654321
using namespace std;

int v,e;

vector<vector<bool>> graph, reverseGraph;
stack<int> node;
vector<bool> visited;
vector<int> scc;
vector<vector<int>> res;

void makeNode(int idx) {
    if (visited[idx])
        return;

    visited[idx] = true;

    for (int next = 1; next <= v; next++) {
        if (graph[idx][next])
            makeNode(next);
    }
    node.push(idx);
}

void dfs(int idx) {
    if (visited[idx])
        return;

    visited[idx] = true;

    for (int next = 1; next <= v; next++) {
        if (reverseGraph[idx][next])
            dfs(next);
    }
    scc.push_back(idx);
}


int main(void) {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    cin >> v >> e;

    graph = vector<vector<bool>>(v + 1, vector<bool>(v + 1, 0));
    reverseGraph = vector<vector<bool>>(v + 1, vector<bool>(v + 1, 0));
    visited = vector<bool>(v + 1, false);
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = reverseGraph[b][a] = true;
    }

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

    visited = vector<bool>(v + 1, false);
    while (!node.empty()) {
        scc = vector<int>();

        int idx = node.top(); node.pop();
        if (visited[idx])
            continue;
        dfs(idx);
        sort(scc.begin(), scc.end());
        res.push_back(scc);
    }

    cout << res.size() << endl;

    for (int i = 0; i < res.size(); i++) {
        for (int j = i + 1; j < res.size(); j++) {
            if (res[i][0] > res[j][0])
                swap(res[i], res[j]);
        }
    }

    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << ' ';
        }
        cout << -1 << endl;
    }




    return 0;
}

• 참조 링크 : https://coloredrabbit.tistory.com/101
• DFS를 두번 돌리는 것이 핵심.
• 다만, 출력시 벡터 순서에 대해서 우선 n^2으로 단순하게 작성했는데, 이 부분에 대해서 해결 방안을 고려해 볼 필요성은 있음. 우선 n^2이어도 문제 없이 작동하기 떄문에 작성했지만....