Pagini recente » Cod sursa (job #1640116) | Cod sursa (job #2266831) | Cod sursa (job #2553513) | Cod sursa (job #1035897) | Cod sursa (job #1787066)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
ifstream f ("sortaret.in");
ofstream t ("sortaret.out");
struct nod{
int pos;
int intrare;
int iesire;
vector <int> vecini;};
vector <nod> v;
vector <int> sol,poz;
queue <int> q;
int n,m;
void bfs(int nod){int curent;
v[nod].intrare=-1;
q.push(nod);
while (!q.empty()){
curent=q.front();
q.pop();
for (unsigned i=0;i<v[curent].vecini.size();++i){
if (v[poz[v[curent].vecini[i]]].intrare>0)
--v[poz[v[curent].vecini[i]]].intrare;
if (v[poz[v[curent].vecini[i]]].intrare==0){
q.push(v[poz[v[v[curent].vecini[i]].pos]].pos);
sol.push_back(v[poz[v[v[curent].vecini[i]].pos]].pos);
v[poz[v[curent].vecini[i]]].intrare=-1;}}
}
}
int main()
{ int x,y;
f>>n>>m;
v.resize(n);
for (int i=0;i<n;++i)
v[i].pos=i;
for (int i=0;i<m;++i){
f>>x>>y;
--x;
--y;
v[x].vecini.push_back(y);
++v[x].iesire;
++v[y].intrare;
}
poz.resize(n);
sort(v.begin(),v.end(),[](nod a,nod b){return a.intrare<b.intrare;});
for (int i=0;i<n;++i)
poz[v[i].pos]=i;
for (auto i:v)
if (!i.intrare){
sol.push_back(i.pos);
bfs(i.pos);
}
for (auto i:sol)
t<<1+i<<" ";
return 0;
}