[BOJ/C++] 2252 줄 세우기

일부 학생들의 키를 비교하여 줄을 세우는 것은 학생들을 노드로 생각하고 노드의 순서를 도출하는 것으로 생각할 수 있습니다.

또한 답이 여러 가지일 경우 아무거나 출력해도 된다는 것은 항상 동일한 결과가 나오지 않는 위상 정렬의 전제와 동일합니다.

위상 정렬의 수행 과정
1. 진입 차수가 0인 노드를 큐에 저장한다
2. 큐에 있는 노드를 탐색 결과에 추가하고 해당 노드가 가르키는 노드의 진입 차수를 1씩 감소시킨다
3. 감소했을 때 진입 차수가 0이 되는 노드를 큐에 삽입한다
4. 큐가 빌 때까지 위를 반복한다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<vector<int>> G;
static vector<int> inDegree;


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

    int N, M;
    cin >> N >> M;

    G.resize(N + 1);
    inDegree.resize(N + 1);

    for(int i=0; i<M; i++)
    {
        int v, e;
        cin >> v >> e;

        G[v].push_back(e);
        inDegree[e]++;
    }

    queue<int> q;

    for(int i=1; i<=N; i++)
    {
        if (inDegree[i] == 0)
            q.push(i);
    }

    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        cout << now << " ";

        for(int next : G[now])
        {
            inDegree[next]--;
            if (inDegree[next] == 0)
                q.push(next);
        }
    }


    return 0;
}