[백준 1766번] 문제집

문제 링크:https://www.acmicpc.net/problem/1766

1766번: 문제집

<문제 풀이> 위상 정렬, 우선순위 큐

indegree가 0인 정점 중에서 가장 번호가 낮은 정점을 먼저 방문해야 되기 때문에 위상 정렬을 우선순위 큐로 구현하면 됩니다.

 

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n, m;
vector<int> adj[32001];
int indegree[32001];
 
class cmp {
public:
    bool operator()(int a, int b) {
        return a > b;
    }
};
 
void bfs() {
    priority_queue<int, vector<int>, cmp > pq;
    for (int i = 1; i <= n; i++) {
        if (indegree[i] == 0) {
            pq.push(i);
        }
    }
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        cout << u << ' ';
        for (auto& v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                pq.push(v);
            }
            
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b; 
        cin >> a >> b;
        adj[a].push_back(b);
        indegree[b]++;
    }
    bfs();
 
    return 0;
}