Cod sursa(job #1922540)

Utilizator adystar00Bunea Andrei adystar00 Data 10 martie 2017 17:49:50
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
vector <pair<int,int> > g[100010];
int n,k,st[500010],seen[500010],viz[500010];
void solve( int node)
{
    int a,fiu;
    a=g[node].size();
    while(a!=0)
    {
        while(a>0&&seen[g[node].back().second]==1)
        {
            g[node].pop_back();
            a--;
        }
        if(a>0)
        {
            fiu=g[node].back().first;
            seen[g[node].back().second]=1;
            g[node].pop_back();
            k++;
            st[k]=fiu;
            node=fiu;
            a=g[fiu].size();
        }
    }
}
int main()
{
    ifstream fin ("ciclueuler.in");
    ofstream fout ("ciclueuler.out");
    int n,i,a,b;
    fin>>n>>k;
    for(i=1; i<=k; i++)
    {
        fin>>a>>b;
        g[a].push_back(make_pair(b,i));
        g[b].push_back(make_pair(a,i));
        viz[a]++;
        viz[b]++;
    }
    for(i=1; i<=n; i++)
        if(viz[i]%2==1)
        {
            fout<<"-1";
            return 0;
        }
    k=1;
    st[k]=1;
    while(k>0)
    {
        solve(st[k]);
        if(k>1)
            fout<<st[k]<<" ";
        k--;
    }
    return 0;
}