https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N,K;
int in_dg[32010];
vector<int> v[32010];
void solve(){
while(true){
priority_queue<int,vector<int>,greater<>> pq;
for(int i=1;i<=N;i++){
if(in_dg[i]==0) pq.push(i);
}
while(!pq.empty()){
int x=pq.top();
cout<<x<<" ";
in_dg[x]=-1;
pq.pop();
for(int i:v[x]){
in_dg[i]--;
if(in_dg[i] == 0) pq.push(i);
}
}
}
return;
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>K;
for(int i=0,u,x;i<K;i++){
cin>>u>>x;
in_dg[x]++;
v[u].push_back(x);
}
solve();
return 0;
}