백준 2252 - 줄세우기.

/*
백준 2252번.
위상정렬을 이용한 가장 기본적인 문제.
*/

/*
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. 
M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 
이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.

학생들의 번호는 1번부터 N번이다.
*/

#include<iostream>
#include<vector>
#include<queue>
#define MAX 32001

using namespace std;

int n, inDegree[MAX], result[MAX]; //노드갯수, 진입차수갯수, 결과값갯수
vector<int> a[MAX]; //정점마다 자신과 연결되어있는 간선

void topologySort()
{
	queue<int> q;
	//진입 차수가 0인 노드를 큐에 삽입.
	for (int i = 1; i <= n; i++)
	{
		if (inDegree[i] == 0)
		{
			q.push(i);
		}
	}

	//정렬이 완전히 수행되려면 정확히 n개의 노드를 방문.
	for (int i = 1; i <= n; i++)
	{
		int x = q.front();
		q.pop();

		result[i] = x;

			for (int j = 0; j < a[x].size(); j++)
			{
				int y = a[x][j];
				//새롭게 진입차수가 0이 된 정점을 큐에 삽입.
				if (--inDegree[y] == 0)//특정원소에 연결되어있는 다른 원소들의 진입차수를 1씩 빼준것
				{
					q.push(y);
				}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		cout << result[i] << ' ';
	}
}

int main()
{
	int m;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int x, y;

		cin >> x >> y;

		a[x].push_back(y);
		
		inDegree[y]++;
	}

	topologySort();

	return 0;
}