[BAE/<JOON> 문제풀이] 2150. Strongly Connected Component

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

핵심::
코사라주 알고리즘 / 타잔 알고리즘 중 코사라주 알고리즘 풀이

SCC란::
강한 연결 방향 그래프

연결 그래프에 존재하는 부분 집합 Z에 속하는 모든 무작위 정점 (A, B)에 대해 A -> B로의 연결이 가능하다면 Z를 SCC라고 한다.

또한 SCC를 구분할 때에는 가장 큰 SCC만 찾도록 한다. 따라서 하나의 그래프에서 SCC를 구했을 때 정점이 겹칠 수 없다.

SCC를 구하는 대표적인 알고리즘은 코사라주 알고리즘과 타잔 알고리즘이 있으며 두 방식 모두 코드에 첨부하였다.

알고리즘은 설명은 별도의 글에서 하겠다.

의견::
솔직히 배울 때 쓸모없을 줄 알았는데 이걸에서 파생하는 문제 많음

타잔 코드::

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

vector<bool> vis, iscc;
vector<int> poslist;
vector<vector<int>> arr;
stack<int> st;
vector<vector<int>> scclist;
int cnt = 1;

bool cmp(vector<int> a, vector<int> b) {
	return a[0] < b[0];
}

int dfs(int x) {
	vis[x] = true;
	poslist[x] = cnt++;
	st.push(x);
	int mp = poslist[x];
	for (auto v : arr[x]) {
		if (!vis[v]) {
			int ret = dfs(v);
			mp = ret < mp ? ret : mp;
		}
		else if (!iscc[v]) {
			mp = mp < poslist[v] ? mp : poslist[v];
		}
	}

	if (poslist[x] == mp) {
		scclist.push_back({});
		while (!st.empty() && st.top() != x) {
			scclist[scclist.size() - 1].push_back(st.top());
			iscc[st.top()] = true;
			st.pop();
		}
		scclist[scclist.size() - 1].push_back(st.top());
		iscc[st.top()] = true;
		st.pop();
		sort(scclist[scclist.size() - 1].begin(), scclist[scclist.size() - 1].end());
	}

	return poslist[x] = mp;
}

int main()
{
	int n, m; cin >> n >> m;	
	vis = vector<bool>(n + 1, false);
	iscc = vector<bool>(n + 1, false);
	poslist = vector<int>(n + 1);
	arr = vector<vector<int>>(n + 1);

	for (int i = 1; i <= m; i++) {
		int s, e; cin >> s >> e;
		arr[s].push_back(e);
	}

	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;		
		//st = stack<int>();
		dfs(i);
	}

	sort(scclist.begin(), scclist.end(), cmp);
	
	cout << scclist.size() << "\n";
	for (int i = 0; i < scclist.size(); i++) {
		for (int j = 0; j < scclist[i].size(); j++) {
			cout << scclist[i][j] << " ";
		}
		cout << "-1\n";
	}

	return 0;
}

 

코사라주 코드::

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(vector<int> a, vector<int> b) {
	return a[0] < b[0];
}

int n, m;
vector<vector<int>> arr;
vector<vector<int>> rarr;
vector<bool> vis;
stack<int> fst;

void dfs(int x) {
	vis[x] = true;
	for (auto v : arr[x]) {
		if (vis[v]) continue;		
		dfs(v);
	}
	fst.push(x);
}

vector<int> find_scc(int x, vector<int> scc) {
	vis[x] = true;
	scc.push_back(x);
	for (auto v : rarr[x]) {
		if (vis[v]) continue;
		scc = find_scc(v, scc);
	}
	return scc;
}



int main()
{
	cin >> n >> m;
	arr.resize(n + 1); rarr.resize(n + 1);

	for (int i = 1; i <= m; i++) {
		int s, d;
		cin >> s >> d;
		arr[s].push_back(d);
		rarr[d].push_back(s);
	}

	vis = vector<bool>(n + 1, false);

	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		dfs(i);
	}		

	vis = vector<bool>(n + 1, false);
	
	vector<vector<int>> scc;

	while (!fst.empty()) {
		auto cur = fst.top(); fst.pop();
		if (vis[cur]) continue;
		auto ret = find_scc(cur, vector<int>());

		sort(ret.begin(), ret.end());
		scc.push_back(ret);
	}	

	sort(scc.begin(), scc.end(), cmp);

	cout << scc.size() << "\n";
	for (int i = 0; i < scc.size(); i++) {
		for (int j = 0; j < scc[i].size(); j++) {
			cout << scc[i][j] << " ";
		}
		cout << "-1\n";
	}

	return 0;
}