Cod sursa(job #2330345)

Utilizator TherevengerkingSurani Adrian Therevengerking Data 28 ianuarie 2019 11:38:56
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

ifstream fin("sortaret.in");

ofstream fout("sortaret.out");

const int Nmax=50000+5;

vector <int >v[Nmax];

vector <int> p;

bool viz[Nmax];

int DP[Nmax];

int Nr[Nmax];

int n,m;

void DFS(int nod)

{

    viz[nod]=1;
    p.push_back(nod);

    for(int i=0;i<v[nod].size();++i)

        if(viz[v[nod][i]]==0 && (DP[v[nod][i]]>DP[nod]+1 or DP[v[nod][i]]==0))

        {

            DP[v[nod][i]]=DP[nod]+1;

            DFS(v[nod][i]);

        }


}

int main()

{

    fin>>n>>m;

    for(int i=1,x,y;i<=m;++i)

    {

        fin>>x>>y;

        v[x].push_back(y);

    }

    //for(int i=1;i<=n;++i,cout<<'\n')

        //for(int j=0;j<v[i].size();++j)

            //cout<<v[i][j]<<" ";

    for(int i=1;i<=n;++i)

    {

        DP[i]=0;

        if(viz[i]==0)

        DFS(i);

    }

    //for(int i=1;i<=n;++i)

        //cout<<DP[i]<<" ";

    for(int i=0;i< p.size();++i)

        fout<<p[i]<<" ";

    return 0;

}