Cod sursa(job #1543160)

Utilizator floreaadrianFlorea Adrian Paul floreaadrian Data 5 decembrie 2015 23:56:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <bitset>
#include <vector>

#define DIM 65536
using namespace std;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

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;
}