(1766) 문제집

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

단계별로 풀어보기

28단계(위상 정렬) 3번째

 

 

 

위상 정렬을 하되 가능한 경우가 여러 개라면 가장 작은 숫자부터 나열하는(사전 순으로 제일 앞에 오는) 위상 정렬을 찾아야 한다.

큐에 들은 여러 원소(가능한 정점) 중 가장 작은 숫자를 먼저 꺼내야 하므로, 큐 대신 우선순위 큐를 쓰면 된다.

 

 

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  priority_queue<int, vector<int>, greater<int>> pq;
  vector adj(n+1, vector<int>());
  vector<int> indegree(n+1), ans;
  
  while(m--){
    int a, b;
    
    cin >> a >> b;
    
    adj[a].push_back(b);
    indegree[b]++;
  }
  
  for(int i=1;i<=n;i++){
    if(!indegree[i]){
      pq.push(i);
    }
  }
  
  while(!pq.empty()){
    int now= pq.top();
    pq.pop();
    
    ans.push_back(now);
    
    for(int next:adj[now]){
      if(!--indegree[next]){
        pq.push(next);
      }
    }
  }
  
  for(int elem:ans)  cout << elem << " ";
  
  return 0;
}