[C++] 백준 2252 줄세우기

#include <iostream>
#include <vector>
#include <queue>
 
std::vector<int> relation[32001] = {};
int isParent[32001] = {};
int N = 0;
int M = 0;
 
int main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cin >> N >> M;
 
    for (int i = 0; i < M; ++i) 
    {
        int child = 0;
        int parent = 0;
        std::cin >> child >> parent;
        relation[child].push_back(parent);
        ++isParent[parent];
    }
 
    std::queue<int> que = {};
 
    for (int i = 1; i <= N; ++i)
    {
        if (!isParent[i])
        {
            que.push(i);
        }
    }
 
    while (!que.empty()) 
    {
        int now = que.front();
        que.pop();
        std::cout << now << ' ';
 
        for (int i = 0; i < relation[now].size(); ++i)
        {
            --isParent[relation[now][i]];
 
            if (!isParent[relation[now][i]])
            {
                que.push(relation[now][i]);
            }
        }
    }
 
    return 0;
}

 

부모가 아닌 번호들은 먼저 입력합니다.

번호들의 부모의 관계를 하나씩 빼주고 그 번호가 0이 되었을 경우

자식 번호들이 이미 다 나왔기 때문에 부모가 아닌 자식으로 판단해서 큐에 다시 입력합니다.