Cod sursa(job #1527747)

Utilizator Alexghita96Ghita Alexandru Alexghita96 Data 18 noiembrie 2015 17:59:47
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
/**
    Given a directed graph with N vertices and M edges, print the topological sort of the graph's vertices (if there is an edge from i to j, then i comes before j in the topological sort).
    1 <= N <= 50,000
    1 <= M <= 100,000
**/

#include <cstdio>
#include <vector>
#include <stack>
 
#define NMAX 50005
 
using namespace std;
 
int N, M;
bool seen[NMAX];
vector <int> graph[NMAX];
stack <int> solution;
 
void read() {
    int vertex1, vertex2;
 
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= M; ++i) {
        scanf("%d %d", &vertex1, &vertex2);
        graph[vertex1].push_back(vertex2);
    }
}
 
void DFS(int vertex) {
    vector <int> :: iterator it;
 
    seen[vertex] = true;
 
    for (it = graph[vertex].begin(); it != graph[vertex].end(); ++it) {
        if (seen[*it] == false) {
            DFS(*it);
        }
    }
    solution.push(vertex);
}
 
void print() {
    while (solution.empty() == false) {
        printf("%d ", solution.top());
        solution.pop();
    }
}
 
int main() {
    read();
    for (int vertex = 1; vertex <= N; ++vertex) {
        if (seen[vertex] == false)
            DFS(vertex);
    }
    print();
}