[BOJ]백준 2150번: Strongly Connected Component(C++)/SCC

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

2150번: Strongly Connected Component

SCC의 기본 문제이다

SCC(Strongly Connected Component)란 그래프 내의 특별한 Connected Component로, 해당 컴포넌트 안의 어떠한 노드 u와 v에 대해 반드시 path가 존재함을 말한다

따라서 directed graph 내에서만 존재할 수 있으며, 해당 SCC를 하나의 큰 노드로 가정하고 그래프를 그리면 DAG가 생성된다

왜인지는 싸피 방학하면 올려야겟다

 

biconnected component와 마찬가지로 dfs를 이용해서 구할 수 있다

#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
using namespace std;
int v, e,s,scc[10005];
bool visit[10005];
vector<int> edge[10005],re[10005];
stack<int> p;
void dfs(int cur) {
	visit[cur] = 1;
	for(auto i:re[cur])
		if (!visit[i])
			dfs(i);
	p.push(cur);
}
void dfs2(int k,int cur) {
	visit[cur] = 1;
	scc[cur] = k;
	for (auto i : edge[cur])
		if (!visit[i])
			dfs2(k,i);
}
int main() {
	scanf("%d%d", &v, &e);
	for (int i = 0,U,V; i < e; i++) {
		scanf("%d%d", &U, &V);
		edge[U].push_back(V);
		re[V].push_back(U);
	}
	for(int i=1;i<=v;i++)
		if(!visit[i])
			dfs(i);
	memset(visit, 0, sizeof(visit));
	while (!p.empty()) {
		int cur = p.top(); p.pop();
		if (visit[cur])continue;
		dfs2(++s,cur);
	}
	printf("%d\n", s);
	for (int i = 1; i <= v; i++) {
		if (scc[i] == -1)continue;
		printf("%d ", i);
		for(int j=i+1;j<=v;j++)
			if (scc[j] == scc[i]) {
				printf("%d ", j);
				scc[j] = -1;
			}
		printf("-1\n");
	}
	return 0;
}