Algorithm/problem

백준 1766번 : 문제집 - 위상정렬 C++ 코드

DingCoDing 2022. 2. 24. 13:43
반응형

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

 

1766번: 문제집

첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주

www.acmicpc.net

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> adj[32001];
int degree[32001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        degree[b]++;
    }

    priority_queue<int> Q;

    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(-i);
        }
    }
    vector<int> ans;

    while (!Q.empty()) {
        int x = -Q.top();
        Q.pop();
        ans.push_back(x);

        for (auto nx : adj[x]) {
            if (--degree[nx] == 0) {
                Q.push(-nx);
            }
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    

    return 0;
}

 

백준 1766

우선순위 큐를 활용한 위상정렬 문제

반응형