Pagini recente » Cod sursa (job #2991066) | Cod sursa (job #2282089) | Cod sursa (job #1669355) | Cod sursa (job #391712) | Cod sursa (job #906136)
Cod sursa(job #906136)
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
vector <int> G[100001],L;
long viz[100001],deg[100001],n,m,i;
queue <int> S;
void read(){
int x,y;
fi >> n >> m;
for (i=1; i<=m; i++){
fi >> x >> y;
G[x].push_back(y); deg[x]++;
G[y].push_back(x); deg[y]++;
}
}
void bfs(int nod){
queue <int> Q;
Q.push(nod); viz[nod]=1;
while (!Q.empty()){
nod=Q.front(); Q.pop();
vector <int>::iterator it;
for (it=G[nod].begin(); it!=G[nod].end(); it++)
if (!viz[*it]) {
viz[*it]=1;
Q.push(*it);
}
}
}
int conex(){
bfs(1);
for (i=1; i<=n; i++)
if (!viz[i]) return 0;
return 1;
}
int eulerian(){
if(!conex()) return 0;
for (i=1; i<=n; i++)
if (deg[i]%2) return 0;
return 1;
}
void sterge(int v,int w){
deg[v]--,deg[w]--;
G[v].pop_back();
vector <int>::iterator it;
for (it=G[w].begin(); it!=G[w].end(); it++)
if (*it==v){
G[w].erase(it);
break;
}
}
void euler(int v){
while (!G[v].empty()){
int w=G[v].back();
S.push(v);
sterge(v,w);
v=w;
}
}
int rez(){
if (!eulerian()) return 0;
int v=1;
do {
euler(v);
v=S.front(); S.pop();
L.push_back(v);
}while (!S.empty());
return 1;
}
void write(int v){
if (!v) fo << "-1\n";
vector <int>::iterator it;
for (it=L.begin(); it!=L.end(); it++)
fo << *it << " ";
}
int main(){
read();
write(rez());
return 0;
}