Pagini recente » Cod sursa (job #1410102) | Cod sursa (job #1633934) | Cod sursa (job #214804) | Cod sursa (job #2550250) | Cod sursa (job #3199351)
#include <bits/stdc++.h>
struct node : std::vector<int> {
int in_deg = 0;
};
std::vector<int> toposort(std::vector<node> vec, int start) {
std::queue<int> free; free.push(start);
std::vector<int> out; out.reserve(vec.size());
while(!free.empty()) {
auto& nod = vec[free.front()];
out.emplace_back(free.front());
free.pop();
//std::random_shuffle(nod.begin(), nod.end());
for(auto v : nod) {
if(--vec[v].in_deg == 0) free.push(v);
}
}
return out;
}
int main() {
freopen("sortare.in", "r", stdin);
freopen("sortare.out", "w", stdout);
int n, m; std::cin >> n >> m;
std::vector<node> noduri(n + 1);
while(m--) {
int a, b; std::cin >> a >> b;
noduri[a].emplace_back(b);
noduri[b].in_deg++;
}
noduri[0].reserve(n);
for(int i = 1; i <= n; i++) {
noduri[i].in_deg++;
noduri[0].emplace_back(i);
}
auto sortare = toposort(noduri, 0);
for(int i = 1; i <= n; i++) std::cout << sortare[i] << ' ';
return 0;
}