[백준 2150] Strongly Connected Component C++

2150번: Strongly Connected Component

강한 연결 요소

ㅈㅎㄱ 교수님의 알고리즘 수업에서 강한 연결 요소 문제를 해결하기 위한 코사라주 알고리즘을 배우고 이를 적용하는 문제를 풀어보았다.

---

1. 문제 해결 아이디어

Graph

위와 같은 그래프를 Graph라고 하자

 

1. Graph에서 임의의 시작 노드를 잡아서 DFS(시작)를 한다.
   • Graph가 서로 분리된 경우도 생각해야한다.(모든 정점에 대해서 DFS하기)
2. DFS를 하면서 각 정점의 finish time을 저장한다.
3. Graph에서 모든 간선의 방향을 반대로 바꾼 역방향 그래프 rev_Graph를 만든다.
4. finish time이 큰 정점부터, 즉 늦게 끝난 정점부터 rev_Graph에서 DFS를 한다. 이때 생기는 DFS트리들이 각각 하나의 SCC가 된다.

rev_Graph

1번 정점이 가장 늦게 끝났기 때문에 1번부터 rev_Graph에서 DFS를 한다.

• 4번 정점에서 DFS가 종료된다.

 

아직 방문하지 않은 3, 5, 6번 정점 중에 5번 정점이 가장 늦게 끝났기 때문에 5번부터 DFS를 한다.

• 6번 정점을 방문하고 종료된다.

마지막으로 남은 3번에서 DFS를 한다.

위 그림과 같은 SCC를 얻을 수 있게 된다.

---

2. 코드

<+21> : 입력과 동시에 모든 간선의 방향을 반대로 바꾼 rev_Graph도 같이 만든다.

 

<+25> ~ <+39> : Graph에서 dfs를 하면서 가장 먼저 끝난 순서대로 rev_search_seq에 차례대로 push한다. (stack의 역할)

<+41> ~ <+53> :  늦게 끝난 정점부터 rev_Graph를 DFS하면서 DFS 트리를 구한다.

 

<+56> ~ <+59> : 아직 방문하지 않은 모든 정점에 대해서 DFS를 한다.

 

<+61> ~ <+68> : 가장 늦게 끝난 정점(stack의 top)부터 dfs를 해서 DFS 트리를 구하고, 구한 트리를 SCC에 push 한다.

 

<+76> : SCC의 개수를 출력하는걸 깜박해서 30분이나 날렸다..

 

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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

#include <bits/stdc++.h>   //#define pii pair<int, int> using namespace std;   int V, E, dtime = 1; vector<int> Graph[10001]; vector<int> rev_Graph[10001]; vector< vector<int> > SCC; //pii df_time[10001]; vector<int> rev_search_seq;   bool visited[10001], rev_visited[10001];   void input(){     int a, b;     cin >> V >> E;     for(int i = 0; i < E; i++){         cin >> a >> b;         Graph[a].push_back(b);         rev_Graph[b].push_back(a);     } }   void dfs(int now){          visited[now] = true; //    df_time[now].first = dtime++;          for(int i = 0; i < Graph[now].size(); i++){         int next = Graph[now][i];         if(visited[next]) continue;                  dfs(next);              } //    df_time[now].second = dtime++;     rev_search_seq.push_back(now); }   void rev_dfs(int now, vector<int> &temp){          rev_visited[now] = true;     temp.push_back(now);          for(int i = 0; i < rev_Graph[now].size(); i++){         int next = rev_Graph[now][i];         if(rev_visited[next]) continue;                  rev_dfs(next, temp);     }      }   void solve(){     for(int i = 1; i <= V; i++){         if(visited[i]) continue;         dfs(i);     }          vector<int> temp;     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, temp);         SCC.push_back(temp);         temp.clear();     }          for(auto &w : SCC){         sort(w.begin(), w.end());     }     sort(SCC.begin(), SCC.end());               cout << SCC.size() << "\n";          for(auto &w : SCC){         for(auto &k : w){             cout << k << " ";         }         cout << "-1\n";     } }   int main(){     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);          input();     solve();          return 0; }   Colored by Color Scripter

cs

코사라주 알고리즘으로 풀었다.

 

타잔 알고리즘이 구현은 더 어렵지만 확장성이 더 좋다고 하니까

다른 문제는 타잔 알고리즘을 배운 뒤에 그걸로 풀어보겠다.