c++ 백준_2252_"줄 세우기"

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

2252번: 줄 세우기

 

순서가 정해져있는 작업을 처리하는 것이다.

​

게다가

여기서 킬포는 페이지 '출력' 부분에

"답이 여러 가지인 경우에는 아무거나 출력한다."

​

오케 이거는 위상정렬만 쓰면 되겠다.

​

위상정렬을 사용해 출력만 해주면 되는 문제였다.

 

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

void line(vector<vector<int>> stdt, vector<int> node,int N) {

	queue<int> q;

	vector<bool> visit(N + 1,false);
	for (int i = 1; i <= N; i++) {
		if (!node[i])
			q.push(i);
	}

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

		cout << x << " ";
		if (visit[x])
			continue;

		visit[x] = true;

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

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

		}
	}
}

int main(void) {


	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<vector<int>> stdt(N+1);
	vector<int> node(N + 1,0);
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		stdt[a].push_back(b);
		node[b]++;
	}

	line(stdt, node, N);

}