Cod sursa(job #2819708)

Utilizator andreea_07Andreea Georgescu andreea_07 Data 18 decembrie 2021 21:07:06
Problema Ciclu Eulerian Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");

vector <vector<pair<int,int>>> v;
vector<int> drum;

bool muchii_viz[500001];

int n,m,x,y,poz=1,grad[500001];



void ciclu_eulerian(int s)
{
    while(!v[s].empty())
    {
        x=v[s].front().first;
        y=v[s].front().second;
        v[s].erase(v[s].begin());
        if(muchii_viz[y]==0)
        {
            muchii_viz[y]=1;
            ciclu_eulerian(x);
        }
    }
     drum.push_back(s);
}

int main()
{
    int i;
    fin>>n>>m;

    v.resize(100001);

    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
        grad[x]++;
        grad[y]++;

    }

    for(i=1;i<=n;i++)
    {
        if(grad[i]%2==1)
        {
            fout<<-1;
            break;
        }
    }

    ciclu_eulerian(1);

    for(i=1;i<drum.size(); i++)
    {
        fout<<drum[i]<<" ";
    }
    return 0;
}