kosaraju_scc_algorithm.cpp

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define N_NODE 11
#define INF 9999999
// 그래프와 역방향 그래프
vector<int> adjList[N_NODE], transList[N_NODE];
void addEdge(int u, int v){
	adjList[u].push_back(v);
	transList[v].push_back(u);
}
// 스택
stack<int> st;
// 방문여부
vector<bool> visited(N_NODE, false);
// SCC 번호
vector<int> sccId(N_NODE);
// SCC 카운터
int sccCnt = 0;
// DFS 하면서 마지막에 stack에 추가한다.
// stack에는 위상정렬의 역순으로 저장된다.
void dfs(int here){
	visited[here] = true;
	for(int there : adjList[here]){
		if(!visited[there]) dfs(there);
	}
	st.push(here);
}
// 역방향 그래프를 방문하면서 SCC 번호를 부여한다.
void setSCC(int here){
	sccId[here] = sccCnt;
	visited[here] = true;
	for(int there : transList[here]){
		if(!visited[there]) setSCC(there);
	}
}
void kosaraju(){
	// 스택 채우기
	fill(visited.begin(), visited.end(), false);
	for(int i=0;i<N_NODE;i++) if(!visited[i]) dfs(i);
	// 원 그래프의 위상정렬의 역순으로
	// 역방향 그래프를 방문하며 SCC 번호를 부여한다.
	fill(visited.begin(), visited.end(), false);
	while(!st.empty()) {
		int here = st.top();
		st.pop();
		if(!visited[here]){
			setSCC(here);
			sccCnt++;
		}
	}
}
int main(){
	// 그래프 생성
	addEdge(1, 0);
	addEdge(0, 2);
	addEdge(2, 1);
	addEdge(1, 4);
	addEdge(4, 7);
	addEdge(4, 5);
	addEdge(5, 8);
	addEdge(8, 4);
	addEdge(0, 3);
	addEdge(3, 6);
	addEdge(3, 9);
	addEdge(6, 9);
	addEdge(9, 10);
	addEdge(10, 6);
	addEdge(6, 7);
	kosaraju();
	for(int i=0;i<N_NODE;i++){
		cout << i << ", scc id : " << sccId[i] << "\n";
	}
	return 0;
}