위상정렬은 어떤 일을 하는 순서를 찾는 알고리즘입니다.

각각의 일의 선후관계가 복잡하게 얽혀있을 때 각각 일의 선후관계를 유지하면서 전체 일의

순서를 짜는 알고리즘입니다.

만약 아래와 같은 일의 순서를 각각 지키면서 전체 일의 순서를 정한다면

1 4 //1번일을 하고 난 후 4번일을 해야한다.\\

5 4\\

4 3\\

2 5\\

2 3\\

6 2

전체 일의 순서는 1, 6, 2, 5, 4, 3과 같이 정할 수 있다. 전체 일의 순서는 여러 가지가 있습

니다 그 중에 하나입니다.

첫 번째 줄에 전체 일의 개수 N과 일의 순서 정보의 개수 M이 주어집니다.

두 번째 줄부터 M개의 정보가 주어집니다.

전체 일의 순서를 출력합니다.

6 6\\

1 4\\

5 4\\

4 3\\

2 5\\

2 3\\

6 2

1 6 2 5 4 3

``` Cpp

#include <iostream>

#include <fstream>

#include <vector>

#include <algorithm>

#include <queue>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

ifstream cin;

cin.open("input.txt");

int n = 0, m = 0, a = 0, b = 0, score = 0;

cin >> n >> m;

vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));

// degree[i]: i번 작업을 하기전 해야하는 사전 작업 갯수

vector<int> degree(n + 1);

queue<int> Q;

for (int i = 0; i < m; i++) {

cin >> a >> b;

graph[a][b] = 1;

degree[b]++;

}

for (int i = 1; i <= n; i++) {

// 사전에 해야할 작업이 없을 경우 Q에 넣어두고 곧바로 처리할 작업으로 예약해 놓는다.

if (degree[i] == 0) Q.push(i);

}

while (!Q.empty()) {

int now = Q.front();

Q.pop();

cout << now << " ";

for (int i = 1; i <= n; i++) {

// 현재(now) 작업이 사전에 처리해야할 작업인 대상을 찾아서 감소 시켜준다.

// 왜냐하면 사전 작업이 끝났기 때문에

if (graph[now][i] == 1) {

degree[i]--;

if (degree[i] == 0) {

Q.push(i);

}

}

}

}

return 0;

}