Cod sursa(job #1934526)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 21 martie 2017 16:36:22
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define mod 1000000007
 
using namespace std;

int n, m;
vector < int > V[100100], r;
int x[500500], y[500500], rs[500100], cnt = 1;
bool v[500500];

void euler(int node)
{
    rs[cnt] = node;
    while (cnt)
    {
    	node = rs[cnt];
    	while (V[node].size())
    	{
    		int curr = V[node].back();
    		V[node].pop_back();
    		if (!v[curr])
    		{
    			v[curr] = 1;
    			rs[++cnt] = x[curr] ^ y[curr] ^ node;
				node = x[curr] ^ y[curr] ^ node; 
			}
		}
		r.pb(rs[cnt--]);
	}
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream cin("ciclueuler.in");
    ofstream cout("ciclueuler.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i];
        V[x[i]].pb(i);
        V[y[i]].pb(i);
    }
    for (int i = 1; i <= n; i++) if (V[i].size() & 1) return cout << -1, 0;
	euler(1);
	for (auto it : r) cout << it << " ";
	return 0;
}