백준 - 2150 (Strongly Connected Component) [C++]

 이 문제는 유향 그래프의 강한 연결 요소들을 찾는 기본 문제이다. 딱히 주의할 점은 없지만 하나 있다면 출력에서 각 강한 연결 요소들 안에서의 정렬도 해야하지만 강한 연결 요소들간의 정렬도 필요하다는 것이다. 강한 연결 요소를 찾는 알고리즘은 O(V + E)인데, 이 문제의 입력은 V 가 최대 10000, E가 최대 100000이므로 2초의 시간이면 충분하다.

 

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

int v, e;
vector<int> edges[10001];
vector<int> transpose[10001];
vector<bool> visited;
stack<int> st;
vector<int> tempNodes;
vector<vector<int>> answer;

void dfs(int start)
{
	visited[start] = true;

	for (int i = 0; i < edges[start].size(); i++)
	{
		int next = edges[start][i];

		if (!visited[next])
		{
			dfs(next);
		}
	}

	st.push(start);
}

void transDfs(int start)
{
	visited[start] = true;

	for (int i = 0; i < transpose[start].size(); i++)
	{
		int next = transpose[start][i];

		if (!visited[next])
		{
			transDfs(next);
		}
	}

	tempNodes.push_back(start);
}

void input()
{
	cin >> v >> e;

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

		cin >> a >> b;
		edges[a].push_back(b);
		transpose[b].push_back(a);
	}

	visited = vector<bool>(v + 1, false);

	for (int i = 1; i <= v; i++)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}

	visited = vector<bool>(v + 1, false);

	while (!st.empty())
	{
		int present = st.top();
		st.pop();

		if (!visited[present])
		{
			tempNodes = vector<int>();
			transDfs(present);
			sort(tempNodes.begin(), tempNodes.end());
			tempNodes.push_back(-1);
			answer.push_back(tempNodes);
		}
	}

	cout << answer.size() << '\n';

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

	for (auto a : answer)
	{
		for (auto t : a)
		{
			cout << t << " ";
		}
		cout << '\n';
	}
}

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

	input();

	return 0;
}