2252번: 줄 세우기 - 위상 정렬

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

2252번: 줄 세우기

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int N, M;
vector<int> graph[32001];
int enter[32001]; //해당 노드로 들어올 수 있는 정점 수

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

	cin >> N >> M;
	for (int i{ 1 }; i <= M; i++)
	{
		int A, B; cin >> A >> B;
		graph[A].push_back(B);
		enter[B]++;
	}

	queue<int> qu;
	for (int i{ 1 }; i <= N; i++)
	{
		if (enter[i] == 0) qu.push(i);
		//들어올 수 없는 정점을 qu에 저장
	}

	vector<int> line;
	while (line.size() < N)
	{
		int u = qu.front(); qu.pop();
		line.push_back(u);

		for (int v : graph[u])
		{
			enter[v]--; //u에 연결된 간선을 제거
			if (enter[v] == 0) qu.push(v); 
			//이때 v로 들어올 수 있는 정점이 없다면 v를 qu에 저장
		}
	}

	for (int i : line) cout << i << " ";
}

 

참고 링크

https://anz1217.tistory.com/28

위상 정렬