[ 백준 2552 ] 줄 세우기 (C++)

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

2252번: 줄 세우기

 

위상 정렬을 사용하면 간단하게 풀 수 있는 문제다. 위상정렬에 대한 상세한 내용은 알고리즘 파트에서 확인할 수 있다. 링크 바로가기!

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N, M;
int inDgree[32001] = {0, };
vector<vector<int>> graph(32001);

void topology_sort() {
	queue<int> q;

	for (int i = 1; i <= N; i++) {
		if (inDgree[i] == 0)
			q.push(i); // 진입차수가 0인 노드 push
	}

	for (int rep = 0; rep < N; rep++) {
		if (q.empty()) {
			cout << "비순환 그래프입니다" << endl;
			return;
		}

		int from = q.front();
		cout << from << ' ';
		q.pop();
		for (int i = 0; i < graph[from].size(); i++) {
			int to = graph[from][i];
			inDgree[to]--;
			if (inDgree[to] == 0)
				q.push(to);
		}
	}

}

int main() {
	int a, b;

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		inDgree[b]++;
	}

	topology_sort();

	return 0;
}