Cod sursa(job #3215946)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 15 martie 2024 14:50:44
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
typedef pair<int,int> pii;
int n,m;
pii g[500005];
int self[100005];
unordered_set<int> setik[100005];
vector<int> sol;
void dfs(int nod)
{
    while(!setik[nod].empty())
    {
        int x=*setik[nod].begin();
        setik[nod].erase(setik[nod].find(x));
        int i=(g[x].first^g[x].second^nod);
        setik[i].erase(setik[i].find(x));
        dfs(i);
    }
    while(self[nod])
    {
        sol.push_back(nod);
        self[nod]--;
    }
    sol.push_back(nod);
}
int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0);
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        fin>>a>>b;
        g[i]={a,b};
        if(a==b)
            self[a]++;
        else
        {
            setik[a].insert(i);
            setik[b].insert(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        int lg=setik[i].size();
        if(lg%2==1)
        {
            fout<<-1;
            return 0;
        }
    }
    dfs(1);
    for(int i:sol)
        fout<<i<<' ';
    return 0;
}