Cod sursa(job #1543138)

Utilizator floreaadrianFlorea Adrian Paul floreaadrian Data 5 decembrie 2015 23:21:42
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<iostream>
#include <bitset>
#include <vector>
 
#define DIM 65536
using namespace std;
 
int n,m,x,y, 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 () {
    cin>>n>>m;
    for (int i = 1; i <= m; i ++) {
    	cin>>x>>y;
        Edges[x].push_back(y);
        Rank[y] ++;
    }
 
    for (int i = 1; i <= n; i ++)
        if (!Rank[i]) DFS (i);
 
    vector <int> :: reverse_iterator it;
    for (it = Stack.rbegin(); it != Stack.rend(); it ++)
       cout<<*it<<" ";
 
    return 0;
}