Cod sursa(job #2343175)

Utilizator razvanboabesrazvan boabes razvanboabes Data 13 februarie 2019 19:00:05
Problema Ciclu Eulerian Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cstdio>
using namespace std;
//ifstream in("ciclueuler.in");
//ofstream out("ciclueuler.out");
const int NMAX=500000;
vector <int> G[NMAX+5];
stack <int> st;
int rasp[NMAX+5];
void Eulerian(int node) {
    int other;
    while(!G[node].empty()) {
        st.push(node);
        other=G[node].back();
        G[node].pop_back();
        G[other].erase(find(G[other].begin(),G[other].end(),node));
        node=other;
    }
}
//void dfs(int u) {
//    int v,j;
//    viz[u]=1;
//    for(j=0; j<G[u].size(); j++) {
//        v=G[u][j];
//        if(viz[v]==0)
//            dfs(v);
//    }
//}
int main() {
freopen("ciclueuler.in","r",stdin);
freopen("ciclueuler.out","w",stdout);
///CITIRE GRAF
    int node,a,i,b;
    int n,m;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++) {
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
///VERIFICAM SA FIE CONEX SI SA AIBA TOATE GRADELE PARE
 //dfs(1);
    for(i=1; i<=n; i++)
        if(G[i].size()%2==1) {
            printf("-1");
            return 0;
        }
///AFISARE
    node=1;
    int cnt=1;
    do {
        Eulerian(node);
        node=st.top();
        rasp[cnt++]=node;
        st.pop();
    } while(!st.empty());
    printf("%d ",rasp[cnt-1]);
    cnt-=2;
    for(i=1;i<=cnt;i++)
       printf("%d ",rasp[i]);
    return 0;
}