Cod sursa(job #1041945)

Utilizator arch_enemyAngela Gossow arch_enemy Data 26 noiembrie 2013 13:28:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

#define NMAX 100001

using namespace std;

int N, M, i, node1, node2, lengthList;
int SortedNodes[NMAX];
vector<int> G[NMAX];
bool Used[NMAX];

inline void DFS(int Node) {
    Used[Node] = true;

    for(vector<int>::iterator AdjNode = G[Node].begin(); AdjNode != G[Node].end(); ++AdjNode)
        if(!Used[*AdjNode])
            DFS(*AdjNode);

    SortedNodes[lengthList--] = Node;
}

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

    scanf("%d%d", &N, &M);
    while(M--) {
        scanf("%d%d", &node1, &node2);
        G[node1].push_back(node2);
    }

    memset(Used, false, sizeof(bool));
    lengthList = N;
    for(i = 1; i <= N; ++i)
        if(!Used[i])
            DFS(i);

    for(i = 1; i <= N; ++i)
        printf("%d ", SortedNodes[i]);

    return 0;
}