Cod sursa(job #2533682)

Utilizator valeriucaraselCarasel Valeriu valeriucarasel Data 29 ianuarie 2020 16:01:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

const int N=50001,M=100001;

int vf[M], nrp[N], urm[M], lst[N], q[N],nr,v[N],k;

bool viz[N];

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);
    }
    v[++k]=x;
}

int main()
{
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    int n,m;
    int x,y;
    in>>n>>m;
    for (int i=1;i<=m;i++)
    {
        in>>x>>y;
        adauga(x,y);
    }
    for (int i=1;i<=n;i++)
    {
        if (viz[i]==false) dfs(i);
    }
    for (int i=n;i>=1;i--)
        out<<v[i]<<" ";
    in.close();
    out.close();
    return 0;
}