Cod sursa(job #1539483)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 30 noiembrie 2015 20:52:24
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <cstdio>
#include <bitset>
#include <vector>

#define DIM 65536
using namespace std;

int nrNodes, nrEdges, node1, node2, Rank[DIM];
vector <int> Edges[DIM], Stack; bitset <DIM> Marked;

void DFS (int node) {
    Marked[node] = 1;

    vector <int> :: iterator it;
    for (it = Edges[node].begin(); it != Edges[node].end(); it ++) {
        int nextNode = *it;

        if (!Marked[nextNode])
            DFS (nextNode);
    }

    Stack.push_back(node);
    return;
}

int main () {

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

    scanf ("%d %d",&nrNodes, &nrEdges);
    for (int i = 1; i <= nrEdges; i ++) {
        scanf ("%d %d", &node1, &node2);

        Edges[node1].push_back(node2);
        Rank[node2] ++;
    }

    for (int i = 1; i <= nrNodes; i ++)
        if (!Rank[i]) DFS (i);

    vector <int> :: reverse_iterator it;
    for (it = Stack.rbegin(); it != Stack.rend(); it ++)
        printf ("%d ", *it);

    return 0;
}