[백준 6543] 그래프의 싱크 C++

6543번: 그래프의 싱크

강한 연결 요소

 

코사라주 알고리즘

---

1. 문제 해결 아이디어

[백준 2150] Strongly Connected Component C++

 

이전에 포스팅 했던 문제에서 사용한 '코사라주 알고리즘'을 조금 변형했다.

 

DFS를 통해서 가장 늦게 stack에 들어간 순서를 구하고

간선의 방향이 모두 바뀐 rev_graph에서 dfs를 수행하면서 SCC를 구한다.

 

SCC를 구할 때 각 정점이 몇 번째 SCC인지도 같이 기록한다.

 

rev_graph를 dfs할 때 다음 정점을 이미 방문했고

다음 정점이 현재 SCC에 속한 정점이 아닌 다른 SCC에 속한 정점이라면

다음 정점이 속한 SCC를 초기화 시키면 된다.

---

2. 코드

 

#include <bits/stdc++.h>
 
#define pii pair<int, int>
using namespace std;
 
int V, E, dtime = 1;
vector<int> Graph[5001];
vector<int> rev_Graph[5001];
vector<int> SCC[5001];
vector<int> rev_search_seq;
int SCC_id[5001];
 
bool visited[10001], rev_visited[10001];
 
void dfs(int now){
    
    visited[now] = true;
    
    for(int i = 0; i < Graph[now].size(); i++){
        int next = Graph[now][i];
        if(visited[next]) continue;
        
        dfs(next);
    }
    
    rev_search_seq.push_back(now);
}
 
void rev_dfs(int now, int id){
    
    rev_visited[now] = true;
    SCC[id].push_back(now);
    SCC_id[now] = id;
    
    for(int i = 0; i < rev_Graph[now].size(); i++){
        int next = rev_Graph[now][i];
        if(rev_visited[next]){
            if(SCC_id[next] != id){
                SCC[SCC_id[next]].clear();
            }
            continue;
        }
        
        rev_dfs(next, id);
    }
    
}
 
void solve(){
    for(int i = 1; i <= V; i++){
        if(visited[i]) continue;
        dfs(i);
    }
    
    int scc_id = 0;
    
    for(int i = rev_search_seq.size()-1; i >= 0; i--){
        int now = rev_search_seq[i];
        if(rev_visited[now]) continue;
        rev_dfs(now, scc_id);
        scc_id++;
    }
    
    vector<int> res;
    
    for(int i = 0; i < V; i++){
        for(auto &w : SCC[i]){
            res.push_back(w);
        }
    }
    
    sort(res.begin(), res.end());
    
    for(auto &w : res){
        cout << w << " ";
    }
    cout << "\n";
}
 
void init(){
    for(int i = 0; i < 5001; i++){
        Graph[i].clear();
        rev_Graph[i].clear();
        SCC[i].clear();
    }
    rev_search_seq.clear();
    memset(SCC_id, 0, sizeof(SCC_id));
    memset(visited, 0, sizeof(visited));
    memset(rev_visited, 0, sizeof(rev_visited));
}
 
void input(){
    int a, b;
    while(true){
        cin >> V;
        if(!V) break;
        cin >> E;
        for(int i = 0; i < E; i++){
            cin >> a >> b;
            Graph[a].push_back(b);
            rev_Graph[b].push_back(a);
        }
        
        solve();
        
        init();
    }
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    input();
    
    return 0;
}