(백준 2105번 SCC) (라이님 블로그 대회 알고리즘 따라잡기 22) SCC

백준 2105번

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

 

나동빈님의 블로그글을 토대로 짜본 알고리즘이다.

https://jjo-mathstory.tistory.com/entry/%EB%9D%BC%EC%9D%B4%EB%8B%98-%EB%B8%94%EB%A1%9C%EA%B7%B8-%EB%8C%80%ED%9A%8C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%94%B0%EB%9D%BC%EC%9E%A1%EA%B8%B0-20-%EA%B0%95%ED%95%9C-%EC%97%B0%EA%B2%B0-%EC%9A%94%EC%86%8CStrongly-Connected-Component

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

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

constexpr int MAX = 10001;

int V, E;
int id = 0, disc[MAX];
bool finished[MAX];
vector<int> adj[MAX];
vector<vector<int>> sccs;
stack<int> st;


int dfs(int u) {
	disc[u] = ++id;
	int parent = disc[u];
	
	st.push(u);

	for (int v : adj[u]) {
		if (disc[v] == 0) parent = min(parent, dfs(v));
		if (!finished[v]) parent = min(parent, disc[v]);
	}

	if (disc[u] == parent) {
		vector<int> scc;

		while (true) {
			int t = st.top();
			st.pop();
			scc.push_back(t);
			finished[t] = true;
			if (t == u) break;
		}
		sort(scc.begin(), scc.end());
		sccs.emplace_back(scc);
	}

	return parent;

}

bool operator<(const vector<int>& v1, const vector<int>& v2) {
	return v1[0] < v2[0];
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	memset(disc, 0, sizeof(disc));
	memset(finished, 0, sizeof(finished));

	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);
	}

	sort(sccs.begin(), sccs.end());

	cout <<sccs.size() << "\n";
	
	for (vector<int> v : sccs) {
		for (vector<int>::iterator it = v.begin(); it < v.end(); it++) {
			cout << (*it) << " ";
		}
		cout << "-1\n";
	}
	

	return 0;
}

 

플래티넘은 이 정도 난이도구나..ㅠㅠ 더 열심히 공부해야겠다!!!!