Cod sursa(job #1423909)

Utilizator UAIC_HreapcaVlasNegrusUAIC Hreapca Vlas Negrus UAIC_HreapcaVlasNegrus Data 22 aprilie 2015 23:28:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;

int N, M, x, y, i, vis[50010];
vector<int> V[50010];
deque<int> sol;

void DFS(int X)
{
    vis[X] = 1;
    for(vector<int>::iterator it = V[X].begin(); it != V[X].end(); it++)
        if(!vis[*it])
            DFS(*it);
    sol.push_front(X);
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d", &N, &M);
    while(M--)
    {
        scanf("%d%d", &x, &y);
        V[x].push_back(y);
    }
    for(i = 1; i <= N; i++)
    {
        if(!vis[i])
            DFS(i);
    }
    for(deque<int>::iterator it = sol.begin(); it != sol.end(); it++)
        printf("%d ", *it);
    return 0;
}