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

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

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알고리즘 강의 영상을 보고 C/C++로 풀어본 문제이다.

https://m.blog.naver.com/ndb796/221236952158

26. 강한 결합 요소(Strongly Connected Component)

DFS와 Stack을 이용해서 해결할 수 있다.

#include<iostream>
#include <algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#define endl '\n'
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define ll long long

using namespace std;
typedef struct GraphNode {
	int dest;
	int cost;
	GraphNode* next;
}GraphNode;

typedef struct Graph {
	int count;
	GraphNode* adj;
}Graph;

int V, E;
int id, address[10003];
bool isComplete[10003];
vector<vector<int>> SCC;
stack<int> stk;

void Init_Graph(Graph* gph, int Cnt) {
	gph->count = Cnt;
	gph->adj = (GraphNode*)malloc(sizeof(GraphNode) * (Cnt + 1));
	for (int i = 1; i <= Cnt; i++) {
		gph->adj[i].next = NULL;
	}
}

int AddDirectedlinkedEdge(Graph* gph, int src, int dst, int cost) {
	GraphNode* Temp = (GraphNode*)malloc(sizeof(GraphNode));
	Temp->cost = cost;
	Temp->dest = dst;
	Temp->next = gph->adj[src].next;
	gph->adj[src].next = Temp;
	return 1;
}

int DFS(Graph *gph, int x) {
	address[x] = ++id;
	stk.push(x);

	int Parent = address[x];
	GraphNode* head = gph->adj[x].next;
	while (head) {
		int y = head->dest;
		if (!address[y])
			Parent = min(Parent, DFS(gph, y));
		else if (!isComplete[y])
			Parent = min(Parent, address[y]);
		head = head->next;
	}

	if (Parent == address[x]) {
		vector<int> scc;
		while (1) {
			int t = stk.top();
			stk.pop();
			scc.push_back(t);
			isComplete[t] = true;
			if (t == x) break;
		}
		SCC.push_back(scc);
	}
	return Parent;
}

int main() {
	CUNLINK;
	Graph graph;
	cin >> V >> E;
	Init_Graph(&graph, V);
	while (E--) {
		int From, To;
		cin >> From >> To;
		AddDirectedlinkedEdge(&graph, From, To, 1);
	}

	for (int i = 1; i <= V; i++) {
		if (!isComplete[i]) 
			DFS(&graph, i);
	}
	cout << SCC.size() << endl;
	for (int i = 0; i < SCC.size(); i++) {
		sort(SCC[i].begin(), SCC[i].end());
	}
	sort(SCC.begin(), SCC.end());
	for (int i = 0; i < SCC.size(); i++) {
		for (auto g : SCC[i]) cout << g << " ";
		cout << -1 << endl;
	}
	return 0;
}