Pagini recente » Cod sursa (job #350946) | Cod sursa (job #2028192) | Cod sursa (job #2446748) | Cod sursa (job #724058) | Cod sursa (job #275376)
Cod sursa(job #275376)
#include<cstdio>
#include<stack>
#include<deque>
#include<queue>
using namespace std;
#define INPUT "ciclueuler.in"
#define OUTPUT "ciclueuler.out"
#define NMAX 100001
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
deque<long> List[ NMAX ], Final;
stack<long> Stiva;
queue<long> Bf;
int vis[ NMAX ];
long N, M;
//Read the input data into two <vector> class lists
void readData()
{
long Node1, Node2;
fscanf(fin, "%ld %ld", &N, &M);
for(long i = 0; i < M; ++i)
{
fscanf(fin, "%ld %ld", &Node1, &Node2);
List[ Node1 ].push_back(Node2);
List[ Node2 ].push_back(Node1);
}
}
int conex()
{
Bf.push(1);
vis[ 1 ] = 1;
long Node;
deque<long>::iterator it;
while(!Bf.empty())
{
Node = Bf.front();
Bf.pop();
for(it = List[ Node ].begin(); it != List[ Node ].end(); ++it)
if(!vis[ *it ])
{
Bf.push(*it);
vis[ *it ] = 1;
}
}
for(long i = 1; i <= N; ++i)
if(!vis[ i ])
return 0;
return 1;
}
//Verify if each node has an even degree
int valid()
{
if(!conex())
return 0;
for(long i = 1; i <= N; ++i)
if(List[ i ].size() % 2 != 0)
return 0;
return 1;
}
void remove(long Node1, long Node2)
{
List[ Node1 ].pop_front();
deque<long>::iterator it;
for(it = List[ Node2 ].begin(); it != List[ Node2 ].end(); ++it)
if(*it == Node1)
{
List[ Node2 ].erase(it);
break;
}
}
void euler(long Node)
{
long nNode;
while(!List[ Node ].empty())
{
nNode = List[ Node ].front();
Stiva.push(Node);
remove(Node, nNode);
Node = nNode;
}
}
//Start building the given cycle
void solve()
{
long Node = 1;
do{
euler(Node);
Node = Stiva.top();
Stiva.pop();
Final.push_back(Node);
} while(!Stiva.empty());
deque<long>::iterator it;
for(it = Final.begin(); it != Final.end(); ++it)
fprintf(fout, "%ld ", *it);
fprintf(fout, "\n");
}
int main()
{
readData();
if(!valid())
fprintf(fout, "-1\n");
else
solve();
fclose(fin);
fclose(fout);
return 0;
}