Cod sursa(job #3239275)

Utilizator maryyMaria Ciutea maryy Data 4 august 2024 05:10:51
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int nmax=1e5, mmax=5e5;
int n, m;
vector <pair<int, int>> g[nmax+1];//tin elementul care urmeaza si numarul muchiei dintre ele
vector <int> path;
bitset <mmax+1> vis;
bool check()
{
    for(int i=1; i<=n; i++)
    {
        if(g[i].size()%2==1)
            return 0;
    }
    return 1;
}
void dfsEuler(int node)
{
    while(!g[node].empty())
    {
        int next=g[node].back().first, muchie=g[node].back().second;
        g[node].pop_back();
        if(vis[muchie]==0)
        {
            vis[muchie]=1;
            path.push_back(next);
            dfsEuler(next);

        }
    }
}
int main()
{
    int x, y;
    in>>n>>m;
    for(int i=1; i<=m; i++)
    {
        in>>x>>y;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    int e=check();
    if(e==0)
    {
        out<<-1;
        return 0;
    }
    dfsEuler(1);
    for(int i=1; i<=m; i++)
    {
        if(vis[i]==0)
        {
            out<<-1;
            return 0;
        }
    }
    if(path.size()!=m)
    {
        out<<-1;
        return 0;
    }
    reverse(path.begin(), path.end());
    for(int it:path)
    {
        out<<it<<" ";
    }
    return 0;
}