Algorithm in A..Z - SCC(Kosaraju)

개념

강한 연결 요소(Strongly Connected Component)는 방향 그래프에서 서로 왕복할 수 있는 가장 큰 정접들의 집합입니다.

SCC

---

작동원리

1. 정방향 그래프로 DFS를 하면서 탐색이 끝나는 순으로 스택에 넣는다.

2. 스택에서 하나씩 꺼내면서 역방향 그래프로 DFS를 진행한다.

3. 역방향으로 DFS를 진행하면서 방문하는 정점들이 SCC이다.

---

시간복잡도

1. 정방향 그래프로 DFS -> O(V + E)

2. 역방향 그래프로 DFS -> O(V + E)

 

O(V + E)

---

문제

2150 Strongly Connected Component

www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

---

코드

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;

int v, e;
vector<vector<int>> graph, rgraph;

stack<int> st;
vector<bool> isVisited;
void dfs(int index) {
	for (auto &next : graph[index]) {
		if (!isVisited[next]) {
			isVisited[next] = true;
			dfs(next);
		}
	}

	st.push(index);
}

vector<vector<int>> scc;
void rdfs(int index) {
	for (auto &next : rgraph[index]) {
		if (!isVisited[next]) {
			isVisited[next] = true;
			rdfs(next);
		}
	}

	scc.back().push_back(index);
}

bool oper(const vector<int>& v1, const vector<int>& v2) {
	return v1.front() < v2.front();
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	cin >> v >> e;
	graph.resize(v + 1);
	rgraph.resize(v + 1);
	for (int i = 0; i < e; ++i) {
		int v1, v2;
		cin >> v1 >> v2;

		graph[v1].push_back(v2);
		rgraph[v2].push_back(v1);
	}

	isVisited.resize(v + 1, false);
	for (int i = 1; i <= v; ++i) {
		if (!isVisited[i]) {
			isVisited[i] = true;
			dfs(i);
		}
	}

	fill(isVisited.begin(), isVisited.end(), false);
	while (!st.empty()) {
		auto index = st.top();st.pop();

		if (!isVisited[index]) {
			scc.emplace_back();
			isVisited[index] = true;
			rdfs(index);
		}
	}

	cout << scc.size() << "\n";
	for (auto &ve : scc) {
		sort(ve.begin(), ve.end());
	}
	
	sort(scc.begin(), scc.end(), oper);
	for (auto &ve : scc) {
		for (auto &val : ve) {
			cout << val << " ";
		}

		cout << -1 << "\n";
	}
}