Pagini recente » Cod sursa (job #40748) | Cod sursa (job #412330) | Cod sursa (job #1510146) | Cod sursa (job #1202382) | Cod sursa (job #2751133)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int NMAX = 5 * 1e4 + 2;
vector<int> adj[NMAX];
int in_deg[NMAX];
int main() {
int N, M;
fin >> N >> M;
int i;
int x, y;
for (i = 1; i <= M; ++i) {
fin >> x >> y;
adj[x].push_back(y);
in_deg[y]++;
}
queue<int> q;
vector<int> topo;
for (i = 1; i <= N; ++i) {
if (in_deg[i] == 0) {
q.push(i);
topo.push_back(i);
}
}
/** Kahn */
while(!q.empty()) {
int node = q.front();
q.pop();
for (auto neigh : adj[node]) {
in_deg[neigh]--;
if (in_deg[neigh] == 0) {
q.push(neigh);
topo.push_back(neigh);
}
}
}
// if (topo.size() != N) {
// exit(EXIT_FAILURE);
// }
for (auto elem : topo) {
fout << elem << " ";
}
fout << "\n";
return 0;
}