-
오늘은 라이님의 강한 연결 요소에 대해 알아보았다. 상세한 내용은 Reference를 참고하면 된다.
라이님이 알려준 알고리즘은 Robert Tarjan의 Tarjan 알고리즘이다.
동빈나 선생님의 유튜브와 블로그 글도 매우 큰 도움이 된다!!
(솔직히 이 유튜브 영상 없었으면 이해가 엄-청 오래 걸렸을 것 같다 ㅠㅡㅠ)
타잔 알고리즘) 동빈나님의 블로그에서 변수명을 내가 알아보기 쉽게 변경한 코드!
#include <iostream> #include <vector> #include <stack> #include <algorithm> #include <cstring> // memeset using namespace std; constexpr int MAX = 10000; int id = 0, disc[MAX]; // disc[i](discovery)는 노드 'i'가 DFS에 의해 처음 발견된 시기 의미 bool fin[MAX]; // dfs의 종료 여부 확인(disc는 0이 아니지만 fin이 0일 수 있음) vector<int> adj[MAX]; vector<vector<int>> sccs; stack<int> st; int dfs(int u) { disc[u] = ++id; st.push(u); int parent = disc[u]; for (int v : adj[u]) { if (disc[v] == 0) { parent = min(parent, dfs(v)); } else if (!fin[v]) { parent = min(parent, disc[v]); } } if (parent == disc[u]) { vector<int> scc; while (true) { int t = st.top(); st.pop(); scc.push_back(t); fin[t] = true; if (t == u) break; } sccs.emplace_back(scc); } return parent; } int main() { memset(disc, 0, sizeof(disc)); memset(fin, 0, sizeof(fin)); int v, e; cin >> v >> e; for (int i = 0; i < e; i++) { int from, to; cin >> from >> to; adj[from].push_back(to); } for (int i = 1; i <= v; i++) { if (disc[i] == 0) dfs(i); } cout << "Number of SCCs: " << sccs.size() << endl; for (int i = 0; i < sccs.size(); i++) { cout << i + 1 << "th SCC: "; for (int node : sccs[i]) { cout << node << " "; } cout << endl; } return 0; }
코사라주 알고리즘)
#include <iostream> #include <vector> #include <stack> #include <algorithm> #include <cstring> // memset using namespace std; constexpr int MAX = 10000; vector<int> adj[MAX], rev_adj[MAX]; vector<vector<int>> sccs; stack<int> st; bool visited[MAX]; void dfs1(int u) { visited[u] = true; for (int v : adj[u]) { if (!visited[v]) { dfs1(v); } } st.push(u); } void dfs2(int u, vector<int>& scc) { visited[u] = true; scc.push_back(u); for (int v : rev_adj[u]) { if (!visited[v]) { dfs2(v, scc); } } } int main() { memset(visited, 0, sizeof(visited)); int v, e; cin >> v >> e; for (int i = 0; i < e; i++) { int from, to; cin >> from >> to; adj[from].push_back(to); rev_adj[to].push_back(from); } // 첫 번째 DFS: 원래 그래프에서 수행하여 스택에 노드 푸시 for (int i = 1; i <= v; i++) { if (!visited[i]) { dfs1(i); } } memset(visited, 0, sizeof(visited)); // 두 번째 DFS: 스택에서 노드를 꺼내면서 역방향 그래프에서 SCC 찾기 while (!st.empty()) { int u = st.top(); st.pop(); if (!visited[u]) { vector<int> scc; dfs2(u, scc); sccs.push_back(scc); } } cout << "Number of SCCs: " << sccs.size() << endl; for (int i = 0; i < sccs.size(); i++) { cout << i + 1 << "th SCC: "; for (int node : sccs[i]) { cout << node << " "; } cout << endl; } return 0; }
Reference
1. 라이님 블로그 - 강한 연결 요소(Strongly Connected Component)
2. 동빈나님의 유튜브
https://www.youtube.com/watch?v=H_Cg3-rv7RU&t=58s
3. 동빈나님의 블로그(타잔 알고리즘, 코드 포함)
https://blog.naver.com/ndb796/221241465461
4. 류호석님의 유튜브(Kosaraju의 알고리즘)
'PROGRAMMING > 알고리즘' 카테고리의 다른 글