Cod sursa(job #1199669)

Utilizator lorundlorund lorund Data 20 iunie 2014 10:18:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <vector>
#include <bitset>
#include <set>
#define SIZE 50005
using namespace std;

int N, M;
set<int> graph[SIZE], tgraph[SIZE];
vector<int> tsorted;
bitset<SIZE> vis;

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

    scanf("%d%d", &N, &M);
    for (int i=1; i<=M; ++i){
        int from, to;

        scanf("%d%d", &from, &to);
        graph[from].insert(to);
        tgraph[to].insert(from);
    }
}

void tdfs(int node){
    vis[node] = 1;
    for (set<int>::iterator it=tgraph[node].begin(); it!=tgraph[node].end(); ++it){
        if (!vis[*it]){
            //vis[*it] = 1;
            tdfs(*it);
        }
    }
    tsorted.push_back(node);
}

void tsort(){
    for (int i=1; i<=N; ++i){
        if (!vis[i]){
            tdfs(i);
        }
    }
}

int main()
{
    read();
    tsort();
    for (unsigned i=0; i<tsorted.size(); ++i)
        printf("%d ", tsorted[i]);
    return 0;
}