Cod sursa(job #874056)

Utilizator TeOOOVoina Teodora TeOOO Data 7 februarie 2013 21:00:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <stdio.h>
#include <vector>
using namespace std;

//Constante
const int sz = (int)1e5+1;

//Functii
void dfs(int node);

FILE *in,*out;

//Variabile
int num, edges;
bool visited[sz];

vector <int> next[sz];
vector <int> previous[sz];

int main()
{
    in=fopen("sortaret.in","rt");
    out=fopen("sortaret.out","wt");

    fscanf(in,"%d%d",&num,&edges);
    for(int i=1; i<=edges; ++i)
    {
        int rFrom, rTo;
        fscanf(in,"%d%d",&rFrom,&rTo);
        next[rFrom].push_back(rTo);
        previous[rTo].push_back(rFrom);
    }

    for(int i=1; i<=num; ++i)
        dfs(i);

    fclose(in);
    fclose(out);
    return 0;
}

void dfs(int node)
{
    if(visited[node])
        return;

    vector<int>::iterator it, end = previous[node].end();

    for(it=previous[node].begin(); it!=end; ++it)
        if(!visited[*it])
            return;

    visited[node] = true;
    fprintf(out,"%d ",node);

    end = next[node].end();

    for(it=next[node].begin(); it!=end; ++it)
        dfs(*it);
}