Pagini recente » Cod sursa (job #437363) | Cod sursa (job #2730443) | Monitorul de evaluare | Diferente pentru problema/perm6 intre reviziile 2 si 1 | Cod sursa (job #3304932)
#include <fstream>
#include <vector>
using namespace std;
struct muchie{
int y, i;
};
int grad[100005], f[100005], is[100005], edges[500005];
vector <muchie> v[100005];
vector <int> ras;
void dfs1( int x ){
int i, y;
for( i = 0; i < v[x].size(); i++ ){
y = v[x][i].y;
if( f[y] == 0 ){
f[y] = 1;
dfs1( y );
}
}
}
void dfs2( int x ){
int y, edge;
while( is[x] < v[x].size() ){
edge = v[x][is[x]].i;
y = v[x][is[x]].y;
is[x]++;
if( edges[edge] == 0 ){
edges[edge] = 1;
dfs2( y );
}
}
ras.push_back( x );
}
int main(){
int n, m, i, x, y, ok;
ifstream fin( "ciclueuler.in" );
ofstream fout( "ciclueuler.out" );
fin >> n >> m;
for( i = 0; i < m; i++ ){
fin >> x >> y;
v[x].push_back( { y, i } );
v[y].push_back( { x, i } );
grad[x]++;
grad[y]++;
}
f[1] = 1;
dfs1( 1 );
ok = i = 1;
while( i <= n && ok == 1 ){
if( f[i] == 0 || grad[i] % 2 == 1 ){
ok = 0;
}
i++;
}
if( ok == 0 ){
fout << -1;
}
else{
dfs2( 1 );
ras.pop_back();
for( i = 0; i < ras.size(); i++ ){
fout << ras[i] << ' ';
}
}
return 0;
}