Cod sursa(job #2343156)

Utilizator razvanboabesrazvan boabes razvanboabes Data 13 februarie 2019 18:45:03
Problema Ciclu Eulerian Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
const int NMAX=10000;
vector <int> G[NMAX+5];
stack <int> st;
bool viz[NMAX+5];
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() {

///CITIRE GRAF
    int node,a,i,b;
    int n,m;
    in>>n>>m;
    for(i=1; i<=m; i++) {
        in>>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(viz[i]==0 || G[i].size()%2==1) {
            out<<-1;
            return 0;
        }
///AFISARE
    node=1;
    int cnt=1;
    do {
        Eulerian(node);
        node=st.top();
        rasp[cnt++]=node;
        st.pop();
    } while(!st.empty());
    out<<rasp[cnt-1]<<" ";
    cnt-=2;
    for(i=1;i<=cnt;i++)
         out<<rasp[i]<<" ";
    return 0;
}