백준 2252번 줄세우기 (C++)

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

2252번: 줄 세우기

위상정렬의 예제 문제이다.

예제 1번을 보자.

3 → 2

1 → 3

2 → 3

위상정렬을 적용해보면

1번은 없고

2번은 3번이

3번은 1번과 2번이 먼저 와야한다. 그러므로 진입차수가 0인 1이 들어오고 진입차수가 다음으로 0이되는 2번이 오고 그다음 3번이 온다. 위상정렬의 특성상, 진입차수가 0인 것이 2개이면 dfs bfs 방법에 따라 순서가 바뀔 수 있다. 그래서 문제에서 아무거나 출력하라는 말이 있는 것이다.

정답 코드

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

int N, M;
vector<int> graph[32001];
bool check[32001] = { false, };
int degree[32001];

queue<int> pq;

int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);

cin >> N >> M;

for (int i = 1; i <= N; i++) {
	degree[i] = 0;
}

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

	graph[a].push_back(b);
	degree[b]++;
}

for(int i = 1; i <= N; i++)
	if (degree[i] == 0) { pq.push(i); check[i] = true; }

while (!pq.empty()) {
	int node = pq.front();
	pq.pop();

	cout << node << " ";

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

		if (check[now_node]) continue;

		degree[now_node]--;

		if (degree[now_node] == 0) {
			pq.push(now_node);
			check[now_node] = true;
		}
	}
}
}