Pagini recente » Cod sursa (job #3296563) | Cod sursa (job #987731) | Cod sursa (job #874892) | Cod sursa (job #704841) | Cod sursa (job #2133807)
//#1861 TopSort
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("topsort.in",ios::in);
ofstream fout("topsort.out",ios::out);
#define MAXN 50000
//#define mmax 400000
typedef queue<int> CoadaDeIntregi;
CoadaDeIntregi succesori[MAXN+1],coadaDe0;
int n,m,gradeIn[MAXN+1];
void citire()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
succesori[x].push(y);
gradeIn[y]++;
}
fin.close();
}
void rezolvare()
{
int i;
for(i=1;i<=n;i++)
if(!gradeIn[i])
coadaDe0.push(i);
while(!coadaDe0.empty())
{
i=coadaDe0.front();
fout<<i<<' ';
coadaDe0.pop();
while(!succesori[i].empty())
{
int nc=succesori[i].front();
succesori[i].pop();
gradeIn[nc]--;
if(!gradeIn[nc])
{
coadaDe0.push(nc);
}
}
}
fout<<endl;
fout.close();
}
int main()
{
bool oldstyle=istream::sync_with_stdio(false);
citire();
rezolvare();
oldstyle=istream::sync_with_stdio(oldstyle);
return 0;
}