Pagini recente » Cod sursa (job #832264) | Cod sursa (job #2497899) | Cod sursa (job #322652) | Cod sursa (job #1782961) | Cod sursa (job #1335315)
#include <fstream>
#include <vector>
#define DMAX 50004
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n, m;
int di[DMAX];
vector <int> A[DMAX];
int C[2][DMAX], crt, urm;
void citire();
void sortare_topologica();
int main()
{
citire();
sortare_topologica();
return 0;
}
void citire()
{
int i, x, y;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
A[x].push_back(y);
di[y]++;
}
}
void sortare_topologica()
{
int i, j, lg;
crt=0; urm=1;
C[crt][0]=0;
for(i=1;i<=n;i++)
if(!di[i])
C[crt][++C[crt][0]]=i;
do{
for(i=1;i<=C[crt][0];i++)
{
fout<<C[crt][i]<<' ';
di[C[crt][i]]=-1;
lg=A[C[crt][i]].size();
for(j=0;j<lg;j++)
{
di[A[C[crt][i]][j]]--;
if(!di[A[C[crt][i]][j]])
C[urm][++C[urm][0]]=A[C[crt][i]][j];
}
}
crt=1-crt; urm=1-urm; C[urm][0]=0;
}while(C[crt][0]);
}