Cod sursa(job #668016)
#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;
}