Pagini recente » Cod sursa (job #1974562) | Istoria paginii utilizator/seekhunt1334 | Cod sursa (job #2246738) | Cod sursa (job #3123349) | Cod sursa (job #751146)
Cod sursa(job #751146)
// sortare topologica cu BFS - alocare dinamica
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int i, st, dr, x, n, m, d[50001], U[50001], C[50001];
struct point{
int info;
point *urm;
};
point *G[50001];
void add(int x, int y)
{
point *p;
p=new point;
p->info=y;
p->urm=G[x];
G[x]=p;
}
void citire()
{
int x, y;
f>>n>>m;
for(m; m; --m)
{
f>>x>>y;
add(x, y);
d[y]++;
}
}
int main()
{
citire();
for(i=1; i<=n; ++i)
if(!d[i]) { C[++dr]=i; U[i]=1; }
point *p;
for(st=1; st<=dr; ++st)
{
x=C[st];
for(p=G[x]; p; p=p->urm)
{
d[p->info]--;
if(!d[p->info] && !U[p->info])
{
C[++dr]=p->info;
U[p->info]=1;
}
}
}
for(i=1; i<=n; ++i) g<<C[i]<<" ";
}