Cod sursa(job #2406391)

Utilizator edi9876Negescu Eduard Mihai edi9876 Data 15 aprilie 2019 18:27:10
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

using namespace std;

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

const int N = 50001, M = 100001;

int lst[N], urm[2 * M], vf[2 * M];
int d[N], q[N];
int nrp[N] = {0};
bool viz[N];
int n, nr = 0, dr;

void adauga(int x, int y)
{
    //il adauga pe y in lista de adiacenta a lui x
    ++nr;
    vf[nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
    nrp[y]++;
}

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);
        }
        nrp[y]--;
    }
    q[++dr] = x;
}

int main()
{
    int m;
    in >> n >> m;
    int x, y;
    for(int i = 0; i < m; i++)
    {
        in >> x >> y;
        adauga(x, y);
    }
    for(int i = 1; i <= n; i++)
    {
        if(!viz[i])
        {
            dfs(i);
        }
    }
    for (int i = n; i >= 1; i--)
    {
        out << q[i] << ' ';
    }
    return 0;
}