백준/2252번(위상 정렬)/C++

문제 설명

 

위상 정렬을 구현해볼 수 있는 기본 문제

 

주의할 점이 딱히 없다.

 

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

#define MAX 32010

using namespace std;

int N, M;

int inDegree[MAX];
vector<int> a[MAX];

void input() {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int A, B;
		cin >> A >> B;
		a[A].push_back(B);
		inDegree[B]++;
	}
}

void topologySort() {
	int result[MAX];
	queue<int> q;

	for (int i = 1; i <= N; i++) {
		if (inDegree[i] == 0) q.push(i);
	}

	for (int i = 1; i <= N; i++) {
		int next = q.front();
		q.pop();
		result[i] = next;
		for (int i = 0; i < a[next].size(); i++) {
			int y = a[next][i];
			if (--inDegree[y] == 0) {
				q.push(y);
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		printf("%d ", result[i]);
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	topologySort();
}

 

 

디버깅 기록

: 위상정렬은 모든 정점에 대해 한 번씩 시행된다는 것을 기억하고, result배열에 매 시행마다 차례차례 값을 저장해 나아가면 된다는 것을 알고 있어야 한다. 이전에 방문했던 정점인지 확인할 필요는 없다. 어차피 진입차수가 0이 되기 전까지는 큐에 들어갈 수 없기 때문.