[백준 1766] 문제집

 

#include <stdio.h>
#include <map>
#include <algorithm>
//#include "Windows.h"
#include <iostream>
#include <queue>
#include <functional>
#include <vector>

using namespace std;
 
priority_queue<int,vector<int>,greater<>> q;

int n,m;
int visit[32010];
vector<int> v[32010];
int main(){
    cin>>n>>m;
    for(int i=0 ; i < m ; i++){
        int x,y;
        scanf("%d%d",&x,&y);
        visit[y]++;
        v[x].push_back(y);
    }
    for(int i=1;i<=n; i++){
        if(visit[i]==0){
            q.push(i);
        }
    }
    vector<int> ans;
    while(!q.empty()){
        int now= q.top();
        ans.push_back(now);
        q.pop();
        for(int i=0 ; i<v[now].size(); i++){
            int node= v[now][i];
            if(visit[node]>0){
                visit[node]--;
                if(visit[node]==0){
                    q.push(node);
                }
            }
        }
    }
    for(int i=0 ; i <ans.size();i++){
        printf("%d ",ans[i]);
    }
}

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

1766번: 문제집

요구사항

조건대로 문제 푸는 순서를 구하라

 

풀이

1. 위상 정렬로 먼저 풀어야하는 문제를 연결시켜주고, 먼저 풀어야된다면 visit를 ++

2. 난이도 순으로 풀기 위해 힙을 이용하여 풀이