Cod sursa(job #1966597)

Utilizator mariakKapros Maria mariak Data 15 aprilie 2017 13:32:04
Problema Ciclu Eulerian Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
/*----Eulerian Cycle/Path
    Eulerian Path is a path in graph that visits every edge exactly once.
            cond : graph is connected + exacly 2 nodes with odd degree
    Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
            cond : graph is connected + all nodes have even degree
*/

#include <bits/stdc++.h>
#define maxN 100002

FILE *fin  = freopen("ciclueuler.in", "r", stdin);
FILE *fout = freopen("ciclueuler.out", "w", stdout);

using namespace std;
int N, M;
int gr[maxN];
vector <int> euler;
vector <int> G[maxN];
bitset <maxN> color;

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

void erase_edge(int u, int v){
    for(int i = 0; i < G[u].size(); ++ i)
        if(G[u][i] == v)
            G[u].erase(G[u].begin() + i);
}

void dfs(int node){
    while(G[node].size()){
        int son = G[node][0];
        G[node].erase(G[node].begin());
        erase_edge(son, node);
        if(!color.test(son))
            dfs(son);
    }
    color.set(node);
    euler.push_back(node);
}

int main(){
    scanf("%d %d", &N, &M);
    for(int i = 1; i <= M; ++ i){
        int x, y;
        scanf("%d %d", &x, &y);
        ++ gr[x], ++ gr[y];
        G[x].push_back(y);
        G[y].push_back(x);
    }
    eulerianGraph();
    dfs(1);
    for(int node : euler)
        printf("%d ", node);
    return 0;
}