[백준/BOJ] 백준 2150번 : Strongly Connected Component

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

2150번: Strongly Connected Component

타잔 알고리즘을 이용해 강한 연결 요소 (SCC)를 구해서 문제를 해결했다.

 

코드

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

//강한 연결 요소(SCC)알고리즘 공부
//타잔 알고리즘

int v, e;
vector<int> adj[10001];
vector<int> node_number(10001); //노드마다 특정 번호가 부여됨
vector<int> visited(10001); //방문했는지 체크
vector<int> maked(10001); //scc가 만들어진 정점 체크
vector<vector<int>> scc;
stack<int> st;
int node_number_cnt = 0;

void Pre()
{
	for (int i = 1; i <= 10000; i++)
	{
		visited[i] = 0;
		maked[i] = 0;
	}
}

int Solve(int here)
{
	//방문 표시
	visited[here] = 1;

	//노드에 방문 순서대로 번호 부여
	node_number_cnt++;
	node_number[here] = node_number_cnt;

	st.push(here);

	int parent; //합쳐질 기준이 될 노드의 부여된 번호
	parent = node_number[here];

	for (int i = 0; i < adj[here].size(); i++)
	{
		int there = adj[here][i];

		//there가 방문하지 않은 정점일때
		if (visited[there] == 0)
		{
			parent = min(parent, Solve(there)); //탐색하고 더 작게 부여된 번호를 기준으로 합쳐지도록
		}

		//방문 했었지만 아직 scc가 만들어 지지 않은 정점일때 (현재 처리중인것을 만났을때)
		else if (maked[there] == 0)
		{
			parent = min(parent, node_number[there]); //싸이클이 만들어지는 경우가 이거 뿐이 아닐 수 있으므로 min으로 한다 (예:네모에서 대각선 하나 있는 그래프 생각)
		}
	}

	//자기 자신이 기준이 되는 노드일때
	if (parent == node_number[here])
	{
		vector<int> this_scc;
		while (1)
		{
			int this_node = st.top();
			st.pop();

			this_scc.push_back(this_node);
			maked[this_node] = 1;

			if (this_node == here)
				break;
		}

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

	return parent;
}

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

	Pre();

	cin >> v >> e;

	for (int i = 0; i < e; i++)
	{
		int a, b;

		cin >> a >> b;

		adj[a].push_back(b);
	}

	//방문하지 않은 노드에 대해서 체크한다
	for (int i = 1; i <= v; i++)
	{
		if (visited[i] == 0)
			Solve(i);
	}

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

	cout << scc.size() << "\n";

	for (int i = 0; i < scc.size(); i++)
	{
		vector<int> this_scc = scc[i];

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

	return 0;
}