Cod sursa(job #1251544)

Utilizator andreey_047Andrei Maxim andreey_047 Data 29 octombrie 2014 17:33:15
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <bitset>
#define nmax 500009
using namespace std;
vector<int>G[nmax];
int sol[nmax],n,m,st[nmax],dr[nmax];
bitset<nmax>fol;
inline bool Euler(){
 int i;
 for(i=1;i<=n;i++)
    if(G[i].size()&1) return 0;
  return 1;
}
inline void dfs(int x){
  for(vector<int>::iterator it = G[x].begin();it!=G[x].end();it++){
        if(!fol[*it]){
    fol[*it]=1;
    dfs(st[*it] + dr[*it]-x);
  }
}
 sol[++sol[0]]=x;
}
int main(){
    int i,x,y;
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
      scanf("%d%d",&st[i],&dr[i]);x=st[i];y=dr[i];
      G[x].push_back(i);
      G[y].push_back(i);
    }
    if(!Euler()) {cout <<"-1\n";return 0;}
    dfs(1);
    for(i=1;i<=sol[0];i++)
        cout << sol[i]<<' ';
    return 0;
}