2252-줄 세우기

https://m.blog.naver.com/kks227/220800013823

위상 정렬(Topological Sort) (수정: 2017-06-22)

에서 위상정렬을 공부하고 풀었다.

글에서 쓰여진대로 들어오는 정점을 어떻게 끊을까 싶었는데, 개수만 센다는게 재밌었다.

 

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

2252번: 줄 세우기

#include <cstdio>
#include <vector>
#include <queue>

std::vector<int> graph[32010];
int n, m, a, b, indegree[32010], ans[32010];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < m; i++) {
        scanf("%d %d", &a, &b);
        graph[a].push_back(b);
        indegree[b]++;
    }
    std::queue <int> queue;
    for(int i = 1; i <= n; i++) {
        if(indegree[i] == 0) queue.push(i);
    }
    for(int i = 1; i <= n; i++) {
        ans[i] = queue.front();
        queue.pop();
        for(int next:graph[ans[i]]) if(--indegree[next] == 0) queue.push(next);
    }
    for(int i = 1; i <= n; i++) printf("%d ", ans[i]);
}