Cod sursa(job #2642224)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 14 august 2020 09:07:52
Problema Ciclu Eulerian Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

FILE *f = fopen("ciclueuler.in","r");
FILE *g = fopen("ciclueuler.out","w");

int n,m;
vector<pair<int,int> > graph[100005];
bool used[100005];
int gr[100005];

int main(){

    fscanf(f,"%d %d",&n,&m);

    for(int i= 1;i <= m;i++){
        int x,y;
        fscanf(f,"%d %d",&x,&y);
        gr[y]++;
        gr[x]++;
        graph[x].push_back({y,i});
        graph[y].push_back({x,i});
    }

    for(int i = 1;i <= n;i++){
        if(gr[i] & 1){
            printf("-1\n");
            return 0;
        }
    }

    stack<int> st;

    st.push(1);
    
    vector<int> ans;

    while(!st.empty()){
        int nod = st.top();

        while(graph[nod].empty() == false && used[graph[nod].back().second]){
            graph[nod].pop_back();
        }

        if(graph[nod].empty()){
            ans.push_back(nod);
            st.pop();
        }
        else{
            used[graph[nod].back().second] = true;
            st.push(graph[nod].back().first);
        }
    }

    ans.pop_back();

    for(auto it:ans){
        fprintf(g,"%d ",it);
    }

    fclose(f);
    fclose(g);

    return 0;
}