[BOJ 2252] 줄 세우기

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

2252번: 줄 세우기

---

위 문제는 전형적인 위상 정렬문제이다. 

 

위상 정렬 알고리즘대로 풀면 쉽게 풀 수 있는 문제이다.

---

#include <stdio.h>
#include <vector>
#include <queue>

#define max(a, b) ((a) > (b) ? (a) :(b))

using namespace std;

int n, m;
int indgree[100001];

int main()
{
	vector<vector<int>> g;
	scanf("%d%d", &n, &m);
	g.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);

		g[a].push_back(b);
		indgree[b]++;
	}

	queue<int> q;

	for (int i = 1; i <= n; i++)
	{
		if (indgree[i] == 0)
			q.push(i);
	}

	while (!q.empty())
	{
		int p = q.front(); q.pop();
		printf("%d ", p);

		for (auto s = g[p].begin(); s != g[p].end(); s++)
		{
			if (--indgree[*s] == 0)
				q.push(*s);
		}
	}
}