ABC_223_D - Restricted Permutation

[zeikar]

Problem link

https://atcoder.jp/contests/abc223/tasks/abc223_d

Problem Summary

1부터 N까지 순열 중에 Ai의 위치 < Bi의 위치를 만족시키는 사전 순으로 가장 작은 순열을 구하는 문제.

Solution

잘 보니 위상 정렬 문제이다.

사전 순으로 출력해야 하므로 우선순위 큐로 처리해주고 정답 사이즈가 n이 아니면 사이클이 존재하는 것이므로 -1을 출력하면 된다.

Source Code

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

vector<int> edges[200001];
int indegree[200001];

int main() {
	int n, m;

	cin >> n >> m;

	while (m--)
	{
		int a, b;
		cin >> a >> b;

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

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

	while (!que.empty())
	{
		int node = -que.top();
		que.pop();
		ans.push(node);

		for (int i = 0; i < edges[node].size(); i++)
		{
			int next = edges[node][i];

			indegree[next]--;

			if (indegree[next] == 0)
			{
				que.push(-next);
			}
		}
	}

	if (ans.size() != n)
	{
		cout << -1 << endl;
	}
	else
	{
		while (!ans.empty())
		{
			cout << ans.front() << ' ';
			ans.pop();
		}
		cout << endl;
	}
}