1766(문제집)
//
// main.cpp
// algorithmtest
//
// Created by 최동규 on 2020/09/13.
// Copyright © 2020 최동규. All rights reserved.
//
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;
vector<int> v[32000];
int check[32000];
int main(int argc, const char * argv[]) {
// insert code here...
// freopen("input", "r", stdin);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int a,b;
cin >> a >> b;
a--;
b--;
v[a].push_back(b);
check[b] += 1;
}
priority_queue<int> pq;
for (int i = 0 ; i < n; i++)
{
if (check[i] == 0)
pq.push(-i);
}
while(!pq.empty())
{
int node = -pq.top();
pq.pop();
cout << node + 1 << " ";
check[node] = -1;
for (int j = 0; j < v[node].size() ;j++)
{
check[v[node][j]] -= 1;
if (check[v[node][j]] == 0)
pq.push(-v[node][j]);
}
}
return 0;
}
고찰
기업코딩 테스트에서 종종 위상정렬이 나와서 위상정렬을 연습한 문제입니다