Pagini recente » Clasament simulare-cartita-10 | Cod sursa (job #3169442) | Cod sursa (job #1856902) | Cod sursa (job #986496) | Cod sursa (job #953671)
Cod sursa(job #953671)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int N,M,x,y,*visited,*deg;
vector<int> *graph;
stack<int> S;
void del (int a,int b)
{
deg[a]--;deg[b]--;
vector<int>::iterator it;
graph[a].erase(graph[a].begin());
for (it=graph[b].begin();it!=graph[b].end();it++)
if (*it==a) {graph[b].erase(it);break;}
}
void DFS(int node)
{
visited[node]=1;
vector<int>::iterator it;
for (it=graph[node].begin();it!=graph[node].end();it++)
if (visited[*it]==0) DFS(*it);
}
bool conex()
{
int i;
DFS(1);
for (i=1;i<=N;i++)
if (visited[i]==0) return false;
return true;
}
bool deg_par()
{
int i;
for (i=1;i<=N;i++)
if (deg[i]%2==1) return false;
return true;
}
void euler(int node)
{ int w;
while (!graph[node].empty())
{
w=*(graph[node].begin());
S.push(node);
del(node,w);
node=w;
}
}
int main()
{
in>>N>>M;
int i;
graph=new vector<int> [N+2];
visited=new int [N+2];
deg=new int [N+2];
for (i=1;i<=N;i++) visited[i]=0,deg[i]=0;
for (i=1;i<=M;i++)
{
in>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
deg[x]++;deg[y]++;
}
int s_node=1;
if (conex() && deg_par())
{while (!S.empty())
{
euler(s_node);
s_node=S.top();
S.pop();
out<<s_node<<" ";
}
}
else out<<"-1";
return 0;
}