[BOJ] 1766 문제집 c++

문제 링크

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

핵심 알고리즘

기본적인 위상정렬은 여러 개의 답이 나올 가능성이 있지만, 해당 문제는 가장 숫자가 작은 번호부터 정렬을 시작하는 문제로 제한을 두어, 답이 1개이다.

이때 deg가 0인 정점을 담는 queue을 오름차순인 priority_queue<int, vector, greater> q로 두어 조건 3번을 만족하게 구현한다.

최종 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <unordered_map>
#include <map>
#include <cmath>
#include <sstream>
using namespace std;

vector<int> adj[32001];
int deg[32001];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    while (m--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        deg[v]++;
    }

    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; i++)
        if (deg[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int cur = q.top();
        q.pop();

        cout << cur << " ";

        for (auto nxt : adj[cur]) {
            deg[nxt]--;
            if (deg[nxt] == 0)
                q.push(nxt);
        }
    }


}