[boj] 2252 - 줄 세우기 C++(DAG, topological sort)

www.acmicpc.net/problem/2252

2252번: 줄 세우기

간단하게 위상정렬에 대해서 배울 수 있는 문제이다.

사이클이 없는 유향그래프인 DAG를 통해서 선행관계를 구현할 수 있는 알고리즘이 위상정렬이다. 
위상정렬은 출력 방법에 따라서 여러 개의 답이 나올 수 있고, DFS, BFS 방식으로 구현할 수 있는데 BFS가 좀 더 간단해보인다. 
밑의 방식은 BFS방식이며, indegree가 0인 노드를 큐에 넣으면서 노드를 소거하는 식으로 다음 노드 순서를 구할 수 있다. 
DFS의 경우, indegree가 0인 노드에 다다를 때 그 노드의 번호를 출력하는 방식으로 풀 수 있다.

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

int n, m;  // 학생수32000, 비교횟수100000

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> m;
    vector<int> graph[32001];
    vector<int> ind(32001);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        ind[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        if (ind[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << ' ';

        for (int i = 0; i < graph[x].size(); ++i) {
            int y = graph[x][i];
            ind[y]--;
            if (ind[y] == 0) q.push(y);
        }
    }

    return 0;
}