C++ / 백준 / 2252 / 줄 세우기

문제

 

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

2252번: 줄 세우기

 

 

문제풀이

 

위상정렬을 이용하여 풀었다.

진입차수 벡터를 만들어 진입차수가 0인 노드를 큐에 집어넣는다.

큐에서 pop을 하면서 해당 노드에서 다른 노드로 가는 간선들의 개수를 제거한다.

제거하는 도중, 다른 노드의 진입 차수가 0인 다른 노드가 있으면 큐에 집어넣는다.

 

노드 개수만큼 반복이 되지 않으면 사이클이 존재한다는 의미인데, 문제에서 A가 B앞에 서야 된다는 조건 외에 다른 조건은 없으므로 사이클이 존재하지 않을 거라 생각했다.

 

큐에서 pop을 할 때 해당 학생의 번호를 출력하기만 하면 된다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
vector<int>inDegree;
vector<vector<int>>tree;
queue<int>q;
int N;

void topology_sort() {
	for (int idx = 1; idx <= N; ++idx) {
		int student = q.front();
		cout << student << ' ';
		q.pop();
		for (int idx2 = 0; idx2 < tree[student].size(); ++idx2) {
			int next = tree[student][idx2];
			--inDegree[next];
			if (inDegree[next] == 0) q.push(next);
		}		
	}
}

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

	int M(0);
	cin >> N >> M;
	tree = vector<vector<int>>(N + 1);
	inDegree = vector<int>(N + 1, 0);

	int student1(0), student2(0);
	for (int idx = 0; idx < M; ++idx) {
		cin >> student1 >> student2;
		tree[student1].push_back(student2);
		++inDegree[student2];
	}

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

	topology_sort();
}