[백준 BOJ 1766] 문제집

백준 링크

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

풀이

• 우선관계가 주어진 문제는 위상정렬을 이용한다
• 위상정렬: BFS와 비슷하지만 in-degree(현재 노드로 올 수 있는 간선의 개수)를 저장하면서 0일때만 방문
• 낮은 번호의 문제부터 풀어야 하므로 -를 붙여 최소힙을 만든다

코드

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

int n,m;
vector< int > prob[32005];
int ind[32005], check[32005];

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    int a,b;
    for(int i=0;i<m;i++){
        cin >> a >>b;
        prob[a].push_back(b);
        ind[b]++;
    }
    priority_queue<int> pq;
    for(int i=1;i<=n;i++){
        if(ind[i] == 0){
            pq.push(-i);
        }
    }
    int cur;
    while(!pq.empty()){
        cur = -pq.top();
        pq.pop();
        cout << cur <<' ';
        for(int i=0;i<prob[cur].size();i++){
            ind[prob[cur][i]]--;
            if(ind[prob[cur][i]] == 0){
                pq.push(-prob[cur][i]);
            }
        }
    }
}

개선점

•