Pagini recente » Istoria paginii runda/oni_10_bv | Cod sursa (job #1509439) | Cod sursa (job #3134773) | Cod sursa (job #634553) | Cod sursa (job #1586446)
#include <iostream> //G este multigraf. Sa se det. daca G este eulerian.
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
#define MMAX 500005
using namespace std;
vector<int> V[NMAX], grad, C;
vector<bool> viz;
//vector<int> V[NMAX], C, grad;
stack<int> L;
int N, M, nodStart;
void citire()
{
int u,v;
scanf("%d%d", &N, &M);
grad.assign(N+2, 0);
for(int i=1; i<=M; i++)
{
scanf("%d %d", &u, &v);
V[u].push_back(v); grad[u]++;
if(u!=v)
V[v].push_back(u);
grad[v]++;
}
}
bool verificare()
{
for(int i=1; i<=N; i++)
if(grad[i] % 2 == 1)
return 0;
else if(!nodStart)
nodStart=i;
return 1;
}
void afisare()
{
for(int i=0; i<C.size()-1; i++)
cout<<C[i]<<' ';
cout<<'\n';
}
void dfsIterativ(int nod)
{
int nodStiva, vecin;
L.push(nod);
while(!L.empty())
{
nodStiva=L.top();
L.pop();
if(grad[nodStiva]){
viz.assign(N+2, 0);
for(int i=V[nodStiva].size()-1; i>=0; i--)
if(V[nodStiva][i]!=0 && viz[V[nodStiva][i]]==0)
{
vecin = V[nodStiva][i];
V[nodStiva][i]=0;
for(int j=0; j < V[vecin].size(); j++){
if(V[vecin][j]==nodStiva){
V[vecin][j]=0;
break;
}
}
grad[nodStiva]--;
grad[vecin]--;
//if(nodStiva != vecin)
L.push(vecin);
viz[vecin]=1;
//break;
}
}
C.push_back(nodStiva);
}
afisare();
}
int main()
{
freopen("ciclueuler.in", "rt", stdin);
freopen("ciclueuler.out", "wt", stdout);
citire();
if(verificare()==0)
cout<<"-1\n";
else
dfsIterativ(nodStart);
}