Cod sursa(job #1809735)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 19 noiembrie 2016 11:03:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <vector>
#include <iostream>
#define NMAX 50010
using namespace std;

vector<int> G[NMAX];
bool viz[NMAX];
int N, M, NN, a, b, S[NMAX]; 


void dfs(int n) {
    if (viz[n]) {
        return;
    }
    viz[n] = true;
    
    for (vector<int>::iterator it = G[n].begin(); it != G[n].end(); it++) {
        dfs(*it);
    }
    
    S[--NN] = n;
}


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

    scanf("%d %d", &N, &M);
    
    for (int i = 0 ; i < M ; i++) {
        scanf("%d %d", &a, &b);
        G[a].push_back(b);
    }
    
    NN = N;
    for (int i = 0 ; i < N ; i++) {
        dfs(i + 1);
    }
    
    for (int i = 0 ; i < N ; i++) {
        printf("%d ", S[i]);
    }
    
    printf("\n");
    return 0;
}