[백준/BOJ] 백준 2252번 : 줄 세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

위상정렬을 이용하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <set>
#include <string>
#include <queue>
#include <cmath>
#include <map>
using namespace std;

int n, m;
vector<int> indegree(32001, 0);
vector<int> adj[32001];

//위상정렬을 이용
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;

		adj[a].push_back(b);
		indegree[b]++;
	}

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

	vector<int> result;
	while (!q.empty())
	{
		int here = q.front();
		result.push_back(here);

		q.pop();

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i];

			indegree[there]--;

			if (indegree[there] == 0)
				q.push(there);
		}
	}

	for (int i = 0; i < result.size(); i++)
		cout << result[i] << " ";

	return 0;
}