Cod sursa(job #1847003)

Utilizator AnduRazvanMindrescu Andu AnduRazvan Data 14 ianuarie 2017 11:07:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
/*#include <fstream>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
struct nod
{ int info;
  nod *urm;
};
nod *a[50001];
void Add(nod *&prim,int y)
{ nod *q=new nod;
    q->info=y;
    q->urm=prim;
    prim=q;
}
int n,m;int viz[50001],gr[50001],z,cl[50001],ok;
int main()
{ fin>>n>>m;
  int i,k,j;
  for(k=1;k<=m;k++)
    {fin>>i>>j;
     Add(a[i],j);
     gr[j]++;
    }

    ok=0;
    while(ok==0)
    { ok=1;
    for(i=1;i<=n;i++)
    { if(gr[i]==0&&viz[i]==0)
        { ok=0;
            nod *p;
            for(p=a[i];p!=NULL;p=p->urm)
                gr[p->info]--;
            viz[i]=1;
            z++;
            cl[z]=i;
        }
    }
    }
    for(i=1;i<=n;i++)
        fout<<cl[i]<<" ";
    return 0;
} */
#include <fstream>

using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;int viz[50001],gr[50001],z,cl[50001],ok;
int tf[50001];
struct nod
{ int info;
  nod *urm;
};
nod *a[50001];
void Add(nod *&prim,int y)
{ nod *q=new nod;
    q->info=y;
    q->urm=prim;
    prim=q;
}
void DFS(int x)
{ nod *p;viz[x]=1;
  for(p=a[x];p!=NULL;p=p->urm)
    if(viz[p->info]==0) DFS(p->info);
  z++;tf[z]=x;

}

int main()
{ fin>>n>>m;
  int i,k,j;
  for(k=1;k<=m;k++)
    {fin>>i>>j;
     Add(a[i],j);
     }
for(i=1;i<=n;i++)
    if(viz[i]==0) DFS(i);
    for(i=n;i>=1;i--)
        fout<<tf[i]<<" ";
    return 0;
}