문제집 (feat. 백준, 1766번)

문제집
https://www.acmicpc.net/problem/1766

1766번: 문제집

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> arr[32001];
int check[32001]{0};
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M;
    cin >> N >> M;
    for(register int m = 0, a, b; m < M; ++m){
        cin >> a >> b;
        arr[a].push_back(b);
        ++check[b];
    }
    priority_queue<int, vector<int>, greater<int>> q;
    for(register int n = 1; n <= N; ++n)
        if(!check[n])
            q.push(n);
    while(!q.empty()){
        auto pos = q.top(); q.pop();
        cout << pos << ' ';
        for(auto& v : arr[pos]){
            if(--check[v] == 0)
                q.push(v);
        }
    }
	return 0;
}
// *&)*@*

 

반응형

위상정렬을 특성을 활용하여 풀이할 수 있습니다.

문제의 내용이 다르더라도 위상정렬은 우선순위 큐를 활용하는 풀이의 특징이 동일하므로 연습이 필요합니다.