[백준]2252 줄세우기 #위상정렬기본

1. 위상정렬?

 

2. 방법

어떠한 노드의 관점에서 그 노드로 들어오는 간선의 수를 진입차수라고 한다. 그리고 이러한 진입 차수가 0인 노드가 항상 시작 노드가 된다.

기본적인 알고리즘은 이러한 시작노드들을 큐에 넣고, 시작노드들과 연결되어 있는 다음 순서의 노드들 사이에 간선들을 없애며, 그 과정에서 새롭게 진입차수가 0이된 노드들을 다시 큐에 넣는 방식으로 진행된다.

 

3. 소스코드

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

using namespace std;

// 부무노드 개수 저장
int parent[32001];

// togo[i]에는 i가 향하는 정점들을 저장
vector<int> togo[32001];

queue<int> q;

int main() {
	int N, M;
	cin >> N >> M;
	int A, B;

	for (int i = 0; i < M; i++) {
		cin >> A >> B;
		togo[A].push_back(B);
		parent[B]++;
	}
	
	for (int i = 1; i <= N; i++) {
		if (parent[i] == 0) {
			q.push(i);
		}
	}
	int temp;
	while (!q.empty()) {
		temp = q.front(); q.pop();
		cout << temp << " ";
		
		
		for (int i = 0; i < togo[temp].size(); i++) {
			// 부모하나줄이고
			parent[togo[temp][i]]--;
			if (parent[togo[temp][i]] == 0) {
				q.push(togo[temp][i]);
			}
		}
	}


	return 0;
}