백준 / 2252 줄 세우기 C++

www.acmicpc.net/problem/2252

2252번: 줄 세우기

골드2 문제였는데 정답률이 50%가 넘길래 어디 기출문제나 유명한 문제인 줄 알았는데 그냥 쉬운 위상정렬 문제였다.

 

위상정렬을 간단히 말하면, 사이클이 없는 방향 그래프에서 각 노드의 순서를 위배하지 않으면서 노드를 정렬하는 것이다. 간단하게 아래에 설명을 했다.

ghqls0210.tistory.com/96 

백준 / 1516 게임 개발 C++

 

해당 문제는 사이클을 따로 체크할 필요도 없고 뭐 특별한 제약 조건도 없기에 그냥 주어진 입력대로 위상정렬 시켜 출력하면 된다.

 

코드는 다음과 같다.

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

int n, m;
vector<int>student[32001]; // vector : i번 학생보다 큰 학생들
int degree[32001]; // 진입 차수

void make_student()
{
	cin >> n >> m;
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		student[a].push_back(b);
		degree[b]++;
	}
}

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

	make_student();

	// 위상 정렬 시작
	queue<int>q;
	for (int i = 1; i <= n; i++)
		if (degree[i] == 0)
			q.push(i);

	while (!q.empty())
	{
		int num = q.front();
		q.pop();
		cout << num << ' ';
		for (int i = 0; i < student[num].size(); i++) {
			degree[student[num][i]]--;
			if (degree[student[num][i]] == 0)
				q.push(student[num][i]);
		}
	}
}