백준: Class 6 - 2150(DAG에서 Strongly Connected Component 찾기)

</br> DAG에서 Strongly Connected Component 찾기
SCC는 부분집합 안 모든 u->v, v->u가 가능한 걸 말한다
알고리즘 강의에서 배웠었던 기억이 있어서 쉽게 할 수 있었다

노드 하나를 잡고, dfs를 수행하고 마지막 방문 시간을 각각 기록한다
그리고 마지막 방문 시간이 큰 정점부터 역방향으로 dfs를 한다.
그럼 dfs에서 방문되는 노드들끼리가 SCC이고, 따라서 총 시행 횟수는 SCC의 개수가 될 것이다.
</br>

2150: Strongly Connected Component

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

#include <bits/stdc++.h>
#define P pair<int, int>

using namespace std;

vector<int> graph[10001];
vector<int> revgraph[10001];
int visited[10001];
priority_queue<P, vector<P>, less<>> pq;
vector< vector<int> > ans;
int d;

void func(int now){
    for(int i = 0; i < graph[now].size(); i++){
        int nx = graph[now][i];
        if( visited[nx] == 0 ){
            visited[nx] = 1;
            d++;
            func(nx);
        }
    }
    d++;
    pq.push(make_pair(d, now));
}

void func2(int now, int ind){
    for(int i = 0; i < revgraph[now].size(); i++){
        int nx = revgraph[now][i];
        if( visited[nx] == 0 ){
            visited[nx] = 1;
            ans[ind].push_back(nx);
            func2(nx, ind);
        }
    }
}

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

    int v, e;
    cin >> v >> e;
    for(int i = 0; i < e; i++){
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        revgraph[b].push_back(a);
    }

    d = 1;
    for(int i = 1; i <= v; i++){
        if( visited[i] ) continue;
        visited[i] = 1;
        func(i);
    }

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

    int ind = 0;
    while( pq.size() ){
        int now = pq.top().second;
        pq.pop();

        if( visited[now] ) continue;

        vector<int> t = {now};
        ans.push_back(t);
        visited[now] = 1;
        func2(now, ind);
        sort(ans[ind].begin(), ans[ind].end());
        ind++;
    }

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

    cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i++){
        for(int a : ans[i]){
            cout << a << ' ';
        }
        cout << "-1\n";
    }

}

일단 입력 받으면 정방향과 역방향 그래프로 저장하고, 방문되지 않은 노드들에서 dfs를 시행해 마지막 방문 시간을 구한다.
(방문 시간, 번호)로 우선순위 큐에 넣었다. 따라서 pq가 빌 때까지, 역방향 그래프에서 탐색을 시행하면 된다.
</br>

---

좋다
</br>