Cod sursa(job #878519)

Utilizator robertgbrrobertgbr robertgbr Data 14 februarie 2013 15:36:03
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 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;
int mystack[MAXN];
list<int> solution;
void DFS(int i,int num){
    list<int>::iterator it;
    if(!mylist[i].empty()){
        for(it=mylist[i].begin();it!=mylist[i].end();it++){
            if(!vizitat[*it]){
                vizitat[*it]=1;
                num++;
                mystack[num]=*it;
                //mystack.push(*it);
                solution.push_back(*it);
                DFS(*it,num);
                mystack[num]=0;
                num--;
                //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);
    mystack[0]=1;
    solution.push_back(1);
    DFS(1,0);
    for(int i=1;i<=N;i++){
        fprintf(outFile,"%d ",solution.front());
        solution.pop_front();}
    fclose(inFile);
    fclose(outFile);
    return 0;
}