[백준 BOJ] 2252번 - 줄 세우기 (C++)

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

2252번: 줄 세우기

키에 대한 순서를 그릴 때 절대 순환적인 모양이 나오지 않는다. 따라서 순서에 대해 정렬해주는 위상 정렬이 바로 떠올랐다. 위상 정렬에 대해서는 따로 포스팅하도록 하겠다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <queue>
#include <vector>
#include <set>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define max 987654321

using namespace std;

int N, M;
queue<int> q;
vector<int> v[32001];
set<int> s;
int store[32001];
int result[32001];
int m=1;
void topology(){
    for(auto i : s){
        if(store[i]==0)
            q.push(i);
    }
    while(!q.empty()){
        int x = q.front();
        q.pop();
        s.erase(x);
        result[m]=x;
        m++;
        for(int i = 0; i<v[x].size(); i++){
            int y = v[x][i];
            if(--store[y]==0)
                q.push(y);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M;
    for(int i = 1; i<=N; i++){
        s.insert(i);
    }
    int x,y;
    for(int i = 0; i<M; i++)
    {   
        cin>>x>>y;
        store[y]++;
        v[x].push_back(y);
        s.erase(y);
    }
    while(!s.empty()){
        topology();
    }
    for(int i = 1; i<=N; i++){
        cout<<result[i]<<" ";
    }
    return 0;
}