Cod sursa(job #878473)

Utilizator robertgbrrobertgbr robertgbr Data 14 februarie 2013 15:17:26
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
//#include <iostream>
#include <cstdio>
#include <list>
#include <stack>
#define MAXN 50000
#define MAXM 100000

using namespace std;
bool vizitat[MAXN];
int M,N;
list<int> mylist[MAXN];
stack<int> mystack;

list<int> solution;
void DFS(int i){
    list<int>::iterator it;
    if(!mystack.empty()&&!mylist[i].empty()){
        for(it=mylist[i].begin();it!=mylist[i].end();it++){
            if(!vizitat[*it]){
                vizitat[*it]=1;
                mystack.push(*it);
                solution.push_back(*it);
                DFS(*it);
                mystack.pop();}
        }
    }
}
int main()
{
    int x,y;
    FILE *inFile;
    FILE *outFile;
    inFile = fopen("sortaret.in","r");
    outFile= fopen("sortaret.out","w");
    fscanf(inFile,"%d",&N);
    fscanf(inFile,"%d",&M);
    for(int i=1;i<=M;i++){
        fscanf(inFile,"%d",&x);
        fscanf(inFile,"%d",&y);
        mylist[x].push_back(y);
    }
    vizitat[1]=1;
    mystack.push(1);
    DFS(1);
    solution.push_front(1);
    for(int i=1;i<=N;i++){
        fprintf(outFile,"%d ",solution.front());
        solution.pop_front();}
    fclose(inFile);
    fclose(outFile);
    return 0;
}