백준 - 2150번 Strongly Connected Component (C++)

600

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

2150번: Strongly Connected Component

 이번 문제는 강한 결합 요소(Strongly Connected Component) 알고리즘 문제이다. 강한 결합 요소란 간단히 말해 강하게 결합된 정점 집합을 의미한다. 이 문제는 이러한 정점 집합들을 찾는 문제이다. 말만 들으면 어려워 보일 수 있으나, 이 알고리즘 문제 중 가장 기본적인 문제라 생각하며, 그렇기에 생각보다 쉬운 문제이다. 왜냐하면, 별다른 비유 없이 직설적으로 정점과 간선의 정보가 주어지고, 이에 따른 scc 정보를 출력하면 되는 문제이기 때문이다. 이 문제를 풀기 위해 참고한 글은 아래에 기록해 두었다. 특별히 신경쓸 점은, 문제의 조건을 충족시키기 위해서 scc를 별도로 정렬해야 한다는 것이다. 

 

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
#include <deque>
#include <cmath>
#include <stack>
#include <cstring>
#include <typeinfo>
#include <iomanip>
#include <limits.h> 
#include <map>
#pragma warning(disable:4996)

using namespace std;

#define MAX 10001

int V, E;
int id = 1;
int parentNode[MAX];
bool finished[MAX];
vector<int> links[MAX];
vector<vector<int>> sccs;	
stack<int> stk;

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

int Check(int node)
{
	parentNode[node] = id++;
	stk.push(node);

	int parent = parentNode[node];

	for (int i = 0; i < links[node].size(); ++i)
	{
		int linkedNode = links[node][i];

		if (parentNode[linkedNode] == 0)
			parent = min(parent, Check(linkedNode));
		else if (finished[linkedNode] == false)
			parent = min(parent, parentNode[linkedNode]);
	}

	if (parent == parentNode[node])
	{
		vector<int> scc;

		while(true)
		{
			int stackedNode = stk.top();
			stk.pop();

			scc.push_back(stackedNode);
			finished[stackedNode] = true;

			if (node == stackedNode)
				break;
		}

		sccs.push_back(scc);
	}

	return parent;
}

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

	cin >> V >> E;

	for (int i = 0; i < E; ++i)
	{
		int from, to;
		cin >> from >> to;

		links[from].push_back(to);
	} 

	for (int node = 1; node <= V; ++node)
	{
		if (parentNode[node] == 0)
			Check(node);
	}

	for (int i = 0; i < sccs.size(); ++i)
		sort(sccs[i].begin(), sccs[i].end());

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

	cout << sccs.size() << endl;
	
	for (int a = 0; a < sccs.size(); ++a)
	{
		for (int b = 0; b < sccs[a].size(); ++b)
			cout << sccs[a][b] << " ";
		cout << -1 << endl;
	}
    
	return 0;
}

---

참고한 글: https://blog.naver.com/ndb796/221236952158