Cod sursa(job #668016)

Utilizator impulseBagu Alexandru impulse Data 24 ianuarie 2012 09:35:33
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<map>
using namespace std;

#define NMAX 50000
#define MMAX 100000
#define filein "sortaret.in"
#define fileout "sortaret.out"

vector<int> V;
char R[NMAX], P[NMAX];
map<int, vector<int> > Mt;
int N, M;

FILE *fin, *fout;

int dfs(int k)
{
    R[k] = 1;
    V.push_back(k);
    while(V.size() != N)
    {
        bool found = false;
        for(int i = 0; i < Mt[k].size(); i++) {
            int val = Mt[k][i];
            if(R[val] == 0){
                found = true;
                R[val] = 1;
                P[val] = k;
                k = val;
                V.push_back(val);
            }
        }
        if(!found)
        {
            k = P[k];
        }
    }
}

int main()
{
    V.reserve(NMAX);
    fin = fopen(filein, "r");
    fscanf(fin, "%d %d", &N, &M);
    for(int k = 0; k < M; k++)
    {
        int i,j;
        fscanf(fin, "%d %d", &i, &j);
        i--, j--;
        Mt[i].push_back(j);
    }
    fclose(fin);
    dfs(0);
    fout = fopen(fileout, "w");
    for(int i = 0; i < N; i++)
        fprintf(fout, "%d ", V[i] + 1);
    fclose(fout);
    return 0;
}