DFS로 풀어보려 했으나 실패.. 최소 힙을 사용하도록 하자.
진입 차수를 관리하며 0이 되면 pq에 넣고 돌리면 됨.
#include <bits/stdc++.h>
using namespace std;
constexpr int MAX = 32001;
int N, M;
vector<vector<int>> adj;
int indegree[MAX];
vector<int> ans;
priority_queue<int, vector<int>, greater<int>> pq;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
adj = vector<vector<int>>(N+1);
while (M--) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
indegree[b]++;
}
for (int i = 1; i < N+1; i++) {
if (!indegree[i]) pq.push(i);
}
while (!pq.empty()) {
int cur = pq.top();
pq.pop();
ans.push_back(cur);
for (int next : adj[cur]) {
if (!(--indegree[next])) {
pq.push(next);
}
}
}
for (int x : ans) {
cout << x << ' ';
}
return 0;
}
아 그냥 좀 풀지 ㅋㅋ