Cod sursa(job #3255328)

Utilizator AlexandraVarutuValexandra AlexandraVarutu Data 10 noiembrie 2024 12:54:36
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ciclueuler.in");
ofstream fout("ciclueuler.out");
int n,m,x,y,fr[100001],ciclue[500001];
struct muchie{
 int nod,d;
};
vector<muchie>v[500001];
stack<int>st;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }
    for(int i=1;i<=n;i++)
        if(v[i].size()%2!=0){
            fout<<-1;
            return 0;
      }
    st.push(1);
    int nr=0;
    while(!st.empty()){
        int k=st.top();
        int ok=0;
        while(ok==0&&!v[k].empty()){
           int nod=v[k].back().nod;
           int mch=v[k].back().d;
           v[k].pop_back();
           if(fr[mch]==0){
               st.push(nod);
               fr[mch]=1;
               ok=1;
               break;
           }
        }
        if(ok==0){
            ciclue[++nr]=k;
            st.pop();
        }
    }
    if(nr<m+1)
    {
        fout<<-1;
        return 0;
    }
    for(int i=1;i<nr;i++)
        fout<<ciclue[i]<<" ";
    return 0;
}