[백준] 1766: 문제집

mint* 2023. 12. 21. 23:42

728x90

url : 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, a, b;
vector<int> graph[100004];
int indegree[32004];
vector<int> result;

void topologySort(){
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int i=1;i<=n;i++){
        if (indegree[i]==0) pq.push(i);
    }
    while(!pq.empty()){
        int now = pq.top();
        pq.pop();
        result.push_back(now);
        for(int i=0;i<graph[now].size();i++){
            int node = graph[now][i];
            indegree[node]-=1;
            if(indegree[node]==0) pq.push(node);
        }

    }
}

int main(){
    // 1. 입력받기
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> a >> b;
        graph[a].push_back(b);
        indegree[b] += 1;
    }
    // 2. 위상정렬
    topologySort();
    // 3. 결과 출력
    for(int r:result) cout << r << " ";
}

728x90