Cod sursa(job #2512445)

Utilizator Rares31100Popa Rares Rares31100 Data 21 decembrie 2019 09:37:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <fstream>
#include <bitset>
#define Size 100000

using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

int n,m,vf[Size+1],urm[Size+1],last[Size/2+1],nr;
int topSort[Size/2+1],t;
bitset <100001> viz;

void adauga(int from,int to)
{
    vf[++nr]=to;
    urm[nr]=last[from];
    last[from]=nr;
}

void dfs(int nod)
{
    viz[nod]=1;

    for(int i=last[nod];i;i=urm[i])
        if(!viz[ vf[i] ])
            dfs(vf[i]);

    topSort[t--]=nod;
}

int main()
{
    cin>>n>>m;

    for(int i,j,k=1;k<=m;k++)
    {
        cin>>i>>j;

        adauga(i,j);
    }

    t=n;

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

    for(int i=1;i<=n;i++)
        cout<<topSort[i]<<' ';

    return 0;
}