Cod sursa(job #2169155)

Utilizator ZeBuGgErCasapu Andreas ZeBuGgEr Data 14 martie 2018 13:41:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<cstdio>
#include<vector>

using namespace std;

const int NMAX = 50001;

int n,m;
vector<int> vec[NMAX];
bool viz[NMAX];

int an[NMAX], p;

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

    int next;
    while(vec[nod].empty() != true)
    {
        next = vec[nod].back();
        vec[nod].pop_back();

        if(viz[next] == false)
        {
            dfs(next);
        }
    }

    p++;
    an[p] = nod;
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);

    scanf("%d %d", &n, &m);

    int x, y;
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &x, &y);
        vec[x].push_back(y);
    }

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

    for(int i = p; i > 0; i--)
    {
        printf("%d ", an[i]);
    }
}