Pagini recente » Cod sursa (job #2365883) | Cod sursa (job #3149233) | Cod sursa (job #1258362) | Cod sursa (job #1221746) | Cod sursa (job #761930)
Cod sursa(job #761930)
#include <fstream>
#include <list>
#include <stack>
#include <queue>
#define MAX 100050
using namespace std;
list<int> E[MAX], L;
queue<int> Q; stack<int> S;
int grad[MAX], n, m;
char rd[200];
bool visited[MAX];
void citire()
{
ifstream in("ciclueuler.in");
in>>n>>m; in.get(); int a, b, i;
for(;m;m--)
{
in.getline(rd, 200);
a = 0; b = 0;
for(i = 0; rd[i] != ' '; i++)
a = a * 10 + rd[i] - '0';
for(++i; rd[i] != '\0'; i++)
b = b * 10 + rd[i] - '0';
E[a].push_back(b);grad[a]++;
E[b].push_back(a);grad[b]++;
}
in.close();
}
void bfs(int nod)
{
Q.push(nod);
while(!Q.empty())
{
int v = Q.front(); Q.pop();
for(list<int>::iterator it = E[v].begin(); it != E[v].end(); it++)
if(!visited[*it])
{
visited[*it] = true;
Q.push(*it);
}
}
}
bool isEulerian()
{
visited[1] = true; bfs(1);
for(int i = 1; i <= n; i++)
if(!visited[i] || (grad[i] & 1))
return false;
return true;
}
void sterge(int v, int w)
{
grad[v]--;grad[w]--;
E[v].pop_front();
for(list<int>::iterator it = E[w].begin(); it != E[w].end(); it++)
if((*it) == v)
{
E[w].erase(it);
return;
}
}
void euler(int nod)
{
while(!E[nod].empty())
{
int v = E[nod].front();
S.push(nod);
sterge(nod, v);
nod = v;
}
}
int solve()
{
if(!isEulerian())
return -1;
else
{
int v = 1;
do
{
euler(v);
v = S.top(); S.pop();
L.push_back(v);
}while(!S.empty());
return 10;
}
}
void afisare(int ok)
{
ofstream out("ciclueuler.out");
if(ok == -1)
out<<"-1";
else
{
for(list<int>::iterator it = L.begin(); it != L.end(); it++)
out<<(*it)<<" ";
}
out.close();
}
int main()
{
citire();
afisare(solve());
return 0;
}