[BOJ] 백준 2252 줄 세우기

문제 링크

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

풀이

1) $i$번 학생 바로 앞에 서야하는 다른 학생이 있으면 $i$번 학생의 indegree를 증가시켜줍니다.

2) 순서가 확정된 학생들 외에는 자유롭게 세워도 되므로, indegree가 0인 모든 정점을 큐에 넣습니다.

3) 위상 정렬을 돌립니다.

 

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

vvi p;
int indeg[33'333];
int n, m;

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

    cin >> n >> m;
    p.resize(n + 1);
    queue<int> q;
    while (m--) {
        int u, v;
        cin >> u >> v;
        p[u].push_back(v);
        indeg[v]++;
    }
    for (int i = 1; i < n + 1; i++) {
        if (indeg[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        cout << now << ' ';
        for (int next: p[now]) {
            if (--indeg[next] == 0) {
                q.push(next);
            }
        }
    }
}