[C++]백준 - 2150번 문제

2150번: Strongly Connected Component (acmicpc.net)

2150번: Strongly Connected Component

 

2150번 : Strongly Connected Component

---

방향 그래프가 주어졌을 때, 그 그래프를 SCC들로 나누는 프로그램을 작성하시오.

방향 그래프의 SCC는 우선 정점의 최대 부분집합이며, 그 부분집합에 들어있는 서로 다른 임의의 두 정점 u, v에 대해서 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 말한다.

예를 들어 위와 같은 그림을 보자. 이 그래프에서 SCC들은 {a, b, e}, {c, d}, {f, g}, {h} 가 있다. 물론 h에서 h로 가는 간선이 없는 경우에도 {h}는 SCC를 이룬다.

 

입력

---

첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A → B가 된다.

정점은 1부터 V까지 번호가 매겨져 있다.

 

 

출력

---

첫째 줄에 SCC의 개수 K를 출력한다. 다음 K개의 줄에는 각 줄에 하나의 SCC에 속한 정점의 번호를 출력한다. 각 줄의 끝에는 -1을 출력하여 그 줄의 끝을 나타낸다. 각각의 SCC를 출력할 때 그 안에 속한 정점들은 오름차순으로 출력한다. 또한 여러 개의 SCC에 대해서는 그 안에 속해있는 가장 작은 정점의 정점 번호 순으로 출력한다.

 

 

 

---

 

생각해 볼 점

---

SCC 문제입니다.

 

SCC(Strongly Connected Component) (tistory.com)

SCC(Strongly Connected Component)

 

코사라주, 타잔 어느쪽을 이용해도 무방합니다.

 

코드

---

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

//벡터 비교 함수
bool cmp(vector<int> & A, vector<int>& B)
{
	return A[0] < B[0];
}

//DFS를 실행하여 스택을 채움
void dfs(vector<int>*& edges, stack<int> & st, bool *& visited, int const & current)
{
	if (visited[current]) return;
	visited[current] = true;
	for (int next : edges[current])
	{
		if (visited[next]) continue;
		dfs(edges, st, visited, next);
	}
	st.push(current);
}

//역방향 DFS를 통해 SCC를 검출하여 벡터에 채움
void get_ans(vector<int>*& edges, vector<int>& ans, bool*& visited, int const& current)
{
	if (visited[current]) return;
	visited[current] = true;
	ans.push_back(current + 1);
	for (int next : edges[current])
	{
		if (visited[next]) continue;
		get_ans(edges, ans, visited, next);
	}
}

int main()
{
	int V, E;
	scanf("%d %d", &V, &E);

	bool* visited = new bool[V];
	fill_n(visited, V, false);
	vector<int>* edges = new vector<int>[V];
	vector<int>* rev_edges = new vector<int>[V];

	//간선 및 역방향 간선 입력받기
	for (int i = 0; i < E; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		a--; b--;
		edges[a].push_back(b);
		rev_edges[b].push_back(a);
	}

	//스택 채우기
	stack<int> st;
	for (int i = 0; i < V; i++) dfs(edges, st, visited, i);

	vector<vector<int>> ans;
	fill_n(visited, V, false);

	//코사라주 알고리즘
	while (!st.empty())
	{
		if (!visited[st.top()])
		{
			ans.push_back(vector<int>());
			get_ans(rev_edges, ans.back(), visited, st.top());
			sort(ans.back().begin(), ans.back().end());
		}
		st.pop();
	}

	sort(ans.begin(), ans.end(), cmp);
	
	printf("%d\n", ans.size());
	//출력
	for (vector<int> v : ans)
	{
		for (int node : v)
		{
			printf("%d ", node);
		}
		printf("-1\n");
	}

	delete[] visited;
	delete[] edges;
	delete[] rev_edges;
	return 0;
}

 

그 외

---