Cod sursa(job #2526162)

Utilizator andaraluca2001Anda Epure andaraluca2001 Data 18 ianuarie 2020 12:15:25
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;
const int N=50009;
const int M = 100001;
int q[N],d[N],lst[N],vf[M],n,m,L,D,nr,urm[M],sorttop[N],ns;
bool viz[N];
ifstream in("sortaret.in");
ofstream out("sortaret.out");
void adauga(int x, int y)

{

    vf[++nr]=y;
    urm[nr]=lst[x];
    lst[x]=nr;
    //nrp[y]++;
}

void dfs(int x)
{
      viz[x]=true;
      int y;

      for(int p=lst[x];p!=0;p=urm[p])
      {
           y=vf[p];
           if(!viz[y]) dfs(y);

      }
     sorttop[++ns]=x;

}


int main()

{

    in>>n>>m;
    for(int i=1; i<=m; i++)

    {
        in>>L>>D;
        adauga(L,D);

    }

    for(int i=1;i<=n;i++)
    {
        if(!viz[i]) dfs(i);


    }


   for(int i=ns;i>=1;i--) out<<sorttop[i]<<" ";




    return 0;

}