Pagini recente » Cod sursa (job #2441844) | Cod sursa (job #292048) | Cod sursa (job #371718) | Istoria paginii utilizator/latrisha3163 | Cod sursa (job #495866)
Cod sursa(job #495866)
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
typedef unsigned int uint;
using namespace std;
int gr[100001];
int c[500003];
//int ce[500005];
vector<int> a[100001];
int viz[100001];
queue <int> Q;
int p = 1, u = 1, nr;
void ciclu(int x);
void inser();
void df(int k);
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int main()
{
int N, M;
in >> N >> M;
for (int i = 1; i <= M; i++)
{
int x, y;
in >> x >> y;
a[x].push_back(y);
a[y].push_back(x);
gr[x]++;
gr[y]++;
}
df(1);
for (int i = 1; i <= N; i++)
if (gr[i] % 2 || (viz[i] == 0 && gr[i] != 0))
{
out << -1;
return 0;
}
//ce[1] = 1;
u=0;c[u]=1;
do
{
if (gr[c[u]] > 0)
{
ciclu(c[u]);
//inser();
//u += nr - 1;
}
else{
out<<c[u]<<" ";u--;}
}while (u>0);
//for (int i = 1; i <= u-1; i++)
//out << ce[i] << ' ';
}
void ciclu(int x)
{
//nr = 1;
//c[1] = x;
bool ok = true;
int nr=x;
do
{
for (int i = 0; (size_t) i < a[x].size() && ok; i++)
{
u++;
c[u] = a[x][i];
gr[a[x][i]]--;
gr[x]--;
int z = a[x][i];
vector<int>::iterator j = find(a[z].begin(), a[z].end(), x);
a[z].erase(j);
a[x].erase(a[x].begin());
x = z;
break;
}
} while (x!=nr);
out<<x<<" ";u--;
}
/*void inser()
{
for (int i = u; i >= p + 1; i--)
ce[i + nr -1] = ce[i];
for (int i = 2; i <= nr; i++)
ce[p + i - 1] = c[i];
}
*/
void df(int k)
{ int s , v;
Q.push(1),viz[1]=true;
while(!Q.empty() ) {
v = Q.front(),Q.pop(),viz[v] = true;
for(s=0;(size_t)s<a[v].size();s++)
if ( !viz[a[v][s]] )
Q.push(a[v][s]);
}
}
/*void df(int k)
{
viz[k] = 1;
for (int i = 0; (size_t)i < a[k].size(); i++)
if (viz[a[k][i]] == 0)
df(a[k][i]);
}*/