Cod sursa(job #2365630)

Utilizator HaesteinnSabau Florin Vlad Haesteinn Data 4 martie 2019 15:21:04
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include<bits/stdc++.h>

using namespace std;
#define NMAX 100005
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m;
list<int> adj[NMAX];
bool visited[NMAX];
int grad[NMAX];
vector<int> ciclu;


void dfs(int v)
{
    visited[v]=1;
    for(auto it=adj[v].begin();it!=adj[v].end();++it)
    {
        int u=*it;
        adj[v].erase(it);
        --it;
        for(auto it2=adj[u].begin();it2!=adj[u].end();++it2)
            if(*it2==v)
            {
                adj[u].erase(it2);
                break;
            }
        dfs(u);
    }
    ciclu.push_back(v);
    
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int v,u;
        fin>>v>>u;
        adj[v].push_back(u);
        adj[u].push_back(v);
        grad[v]++;
        grad[u]++;
    }
    for(int i=1;i<=n;i++)
        if(grad[i]%2)
        {
            fout<<-1;
            return 0;
        }
    dfs(1);
    for(int i=1;i<=n;i++)
        if(!visited[i])
        {
            fout<<-1;
            return 0;
        }
    ciclu.pop_back();
    for(auto x:ciclu)
        fout<<x<<' ';
    return 0;
}