Cod sursa(job #1782096)
Utilizator | Gaman Eduard-Marian gamanedy | Data | 17 octombrie 2016 19:30:35 |
---|---|---|---|
Problema | Sortare topologica | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.02 kb |
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m,viz[100002],d[100002];
struct nod
{
int v;
nod *urm;
};
nod *L[100002], *p;
int coada[100002];
int i,x,y,c,pr,ul;
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
p=new nod;
p->v=y;
p->urm=L[x];
L[x]=p;
d[y]++;
}
for(i=1;i<=n;i++)
{
viz[i]=0;
}
pr=1;
ul=0;
for(i=1;i<=n;i++)
{
if(d[i]==0)
{
ul++;
coada[ul]=i;
viz[i]=1;
fout<<i<<" ";
}
}
while(pr<=ul)
{
x=coada[pr];
for(p=L[x];p!=0;p=p->urm)
{
y=p->v;
d[y]--;
if(d[y]==0 && viz[y]==0)
{
fout<<y<<" ";
viz[y]=1;
ul++;
coada[ul]=y;
}
}
pr++;
}
return 0;
}