[백준 2252]줄세우기

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

2252번: 줄 세우기

 

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

2252번: 줄 세우기

첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다.

www.acmicpc.net
문제 분류- 위상정렬(자세한건 자료구조 포스팅에!!)



문제해결- 진입차수 파악해서 노드를 정렬



#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N, M;
vector<int>a[32002];
int inDegree[32002];
void topologySort()
{
	int Result[32002] = { 0, };//결과담기
	queue<int>pq;
	//진입차수가 0인것 찾기
	for (int i = 1; i <= N; i++)
	{
		if (inDegree[i] == 0)
		{
			pq.push(i);
		}
	}
	//노드방문다하면 정렬완료
	for (int i = 1; i <= N; i++)
	{
		
		if (pq.empty()) ///비어있으면 사이클
		{
			cout << -1 << endl;
			return ;
		}
		int x = pq.front();
		Result[i] = x;//큐에서꺼내면서 순서 저ㄴ장
		pq.pop(); //노드삭제
		for (int j = 0; j < a[x].size();j++) //연결된간선삭제
		{
			int y = a[x][j];
			if (--inDegree[y] == 0)
			{
				pq.push(y);
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		cout << Result[i] << " ";
	}
	cout << endl;
	return;
}
int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		a[x].push_back(y); //A에서 B 연결
		inDegree[y]++;//진입차수증가
	}
	topologySort();
}