(라이님 블로그 대회 알고리즘 따라잡기 22) 강한 연결 요소(Strongly Connected Component)

오늘은 라이님의 강한 연결 요소에 대해 알아보았다. 상세한 내용은 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)

https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220802519976&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList&photoView=2

2. 동빈나님의 유튜브

https://www.youtube.com/watch?v=H_Cg3-rv7RU&t=58s

 

3. 동빈나님의 블로그(타잔 알고리즘, 코드 포함)

https://blog.naver.com/ndb796/221241465461

 

4. 류호석님의 유튜브(Kosaraju의 알고리즘)

https://youtu.be/iKNkpiQhsE0?si=uXmWwbToDl0deWCP