백준 2252 : 줄 세우기

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

2252번: 줄 세우기

 

현재 정점이 되는 사람보다 키가 작은 사람이 무조건 이미 앞에 존재해야하므로 위상정렬로 해결할 수 있는 문제다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<int> edge[32'001];
int pre_cnt[32'001];
vector<int> ans;

void bfs() {
	int cur, next;
	queue<int> q;

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

	while (!q.empty()) {
		cur = q.front();
		q.pop();

		ans.push_back(cur);
		for (int i = 0; i < edge[cur].size(); i++) {
			next = edge[cur][i];
			--pre_cnt[next];

			if (!pre_cnt[next]) q.push(next);
		}
	}
}

void solution() {
	int m, from, to;
	cin >> n >> m;
	while (m--) {
		cin >> from >> to;
		edge[from].push_back(to);
		++pre_cnt[to];
	}

	bfs();

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << ' ';
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solution();

	return 0;
}

메모리: 4148 kb

시간: 36 ms