Pagini recente » Cod sursa (job #9841) | Cod sursa (job #2380791) | Cod sursa (job #2567861) | Cod sursa (job #1617920) | Cod sursa (job #1314404)
// ciclueulerian
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMax 100005
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n,m;
vector<int> V[NMax];
stack<int> S;
vector<int> sol;
bool viz[NMax];
int deg[NMax];
void dfs(int node) {
viz[node] = true;
for (unsigned i=0;i<V[node].size();i++) {
int vecin = V[node][i];
if (!viz[vecin])
dfs(vecin);
}
}
bool checkEulerian() {
dfs(1);
for (int i=1;i<=n;i++)
if (!viz[i])
return false;
for (int i=1;i<=n;i++)
if (deg[i] % 2 != 0)
return false;
return true;
}
void read() {
f>>n>>m;
for (int i=1;i<=m;i++) {
int x, y;
f>>x>>y;
V[x].push_back(y); deg[x]++;
V[y].push_back(x); deg[y]++;
}
}
void euler( int v ) {
while( true ) {
if( V[v].empty() )
break;
int w = V[v][V[v].size()-1];
S.push( v );
V[v].pop_back();
for (unsigned i=0;i<V[w].size();i++)
if (V[w][i] == v) {
V[w].erase(V[w].begin() + i);
break;
}
v = w;
}
}
int main() {
read();
if (checkEulerian()) {
int v = 1;
do {
euler( v );
v = S.top(); S.pop();
sol.push_back( v );
} while( !S.empty() );
// Afisare
for (unsigned i=0;i<sol.size();i++)
g<<sol[i]<<' ';
} else
g<<-1<<'\n';
f.close(); g.close();
return 0;
}