Pagini recente » Cod sursa (job #1715581) | Cod sursa (job #1715818) | Cod sursa (job #2197696) | Cod sursa (job #546663) | Cod sursa (job #1604520)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
void sortaret(const vector<vector<int>>& graf, vector<int>& rez){
const int n = graf.size();
vector<int> in_deg(n, 0), de_viz;
for(int i = 0; i < n; ++i){
for(int j = 0; j < graf[i].size(); ++j){
++in_deg[graf[i][j]];
}
}
for(int i = 0; i < n; ++i){
if(in_deg[i] == 0){
de_viz.push_back(i);
}
}
while(!de_viz.empty()){
const int cur = de_viz.back();
rez.push_back(cur);
de_viz.pop_back();
for(int i = 0; i < graf[cur].size(); ++i){
--in_deg[graf[cur][i]];
if(in_deg[graf[cur][i]] == 0){
de_viz.push_back(graf[cur][i]);
}
}
}
}
int main()
{
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int n, m;
f >> n >> m;
vector<vector<int>> graf(n);
for(int i = 0, a, b; i < m; ++i){
f >> a >> b;
--a, --b;
graf[a].push_back(b);
}
vector<int> rez;
sortaret(graf, rez);
for(int i = 0; i < rez.size(); ++i){
g << rez[i]+1 << ' ';
}
return 0;
}