Cod sursa(job #2528769)

Utilizator AlexBosneag26Bosneag Alexandru AlexBosneag26 Data 22 ianuarie 2020 15:48:36
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>

using namespace std;

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

const int N = 50001, M = 100001;
int vf[M], urm[M], lst[N], q[N], nrp[N], nr, viz[N], st[M], no;

void adauga(int x, int y)
{
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs(int x)
{
    viz[x] = true;
    for(int p = lst[x]; p != 0; p = urm[p])
    {
        int y = vf[p];
        if(!viz[y])
            dfs(y);
    }
    st[++no] = x;
}



int main()
{
    int n, m, m1, m2, x, y;
    in >> n >> m;
    for(int  i = 1; i <= m; i++)
    {
        in >> m1 >> m2;
        adauga(m1, m2);
        nrp[m2]++;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!viz[i])
            dfs(i);
    }
    for(int i = no; i >= 1; i--)
    {
        out << st[i] << " ";
    }


    return 0;
}