Mai intai trebuie sa te autentifici.
Cod sursa(job #1654940)
Utilizator | Data | 17 martie 2016 16:53:09 | |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.93 kb |
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
const int Nmax=50005;
const int Mmax=100005;
int n,m,a,b,nr,cate,u,primul=-2;
int lst[Nmax],vf[Mmax],urm[Mmax],ordine[Nmax],q[Nmax];
void adauga ( int x , int y ){
nr++;
vf[nr]=y;
urm[nr]=lst[x];
lst[x]=nr;
ordine[y]++;
}
void bfs ( int x ){
int p=0,poz,y;
while ( p < u ){
x=q[p++];
poz=lst[x];
fout<<x<<' ';
while ( poz != 0 ){
y=vf[poz];
poz=urm[poz];
ordine[y]--;
if ( ordine[y] == 0 ){
q[u++]=y;
}
}
}
}
int main()
{
fin>>n>>m;
for ( int i=1 ; i<=m ; i++ ){
fin>>a>>b;
adauga(a,b);
}
for ( int i=1 ; i<=n ; i++ ){
if ( ordine[i] == 0 ){
q[u++]=i;
if ( u == 0 )
primul=i;
}
}
bfs(primul);
}