Cod sursa(job #2439296)

Utilizator CharacterMeCharacter Me CharacterMe Data 15 iulie 2019 16:27:44
Problema Ciclu Eulerian Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
int n, m, i, j;
vector<pair<int, int> > list;
vector<int> graph[100001], cycle;
vector<bool> check;
stack<int> s;
int main()
{
    freopen("ciclueuler.in", "r", stdin);
    freopen("ciclueuler.out", "w", stdout);
    scanf("%d%d", &n, &m);
    list.push_back({0, 0}); check.push_back(false);
    for(i=1; i<=m; ++i){
        int x, y;
        scanf("%d%d", &x, &y);
        graph[x].push_back(i);
        graph[y].push_back(i);
        list.push_back({x, y});
        check.push_back(false);
    }
    for(i=1; i<=n; ++i) if(graph[i].size()%2) {printf("-1"); return 0;}
    s.push(1);
    while(!s.empty()){
        int node=s.top();
        if(graph[node].size()){
            int i=graph[node].back();
            graph[node].pop_back();
            if(check[i]==false){
                check[i]=true;
                int x, y;
                x=list[i].first, y=list[i].second;
                if(x==node) s.push(y);
                else s.push(x);
            }
        }
        else{
            cycle.push_back(node);
            s.pop();
        }
    }
    cycle.pop_back();
    for(auto i:cycle) printf("%d ", i);
    return 0;
}