Cod sursa(job #782388)

Utilizator stefanzzzStefan Popa stefanzzz Data 27 august 2012 19:57:02
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <list>
#include <vector>
#define MAXN 100005
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");

int n,m,u,v,x,y,d[MAXN];
list<int> G[MAXN];
vector<int> st,ciclu;
bool uz[MAXN];

bool eulerian();
void DFS(int p);

int main()
{
    list<int>::iterator it;
    int i;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>u>>v;
        d[u]++;d[v]++;
        G[u].push_back(v);
        G[v].push_back(u);}
    if(eulerian()){
        st.push_back(1);
        while(!st.empty()){
            x=st.back();
            if(!G[x].empty()){
                y=G[x].front();
                G[x].pop_front();
                for(it=G[y].begin();*it!=x;it++);
                G[y].erase(it);
                st.push_back(y);}
            else{
                ciclu.push_back(x);
                st.pop_back();}}
        for(i=0;i<ciclu.size()-1;i++)
            g<<ciclu[i]<<' ';}
    else
        g<<"-1\n";
    f.close();
    g.close();
    return 0;
}

bool eulerian(){
    int i;
    DFS(1);
    for(i=2;i<=n;i++)
        if(!uz[i])
            return 0;
    for(i=1;i<=n;i++)
        if(d[i]%2)
            return 0;
    return 1;}

void DFS(int p){
    list<int>::iterator it;
    uz[p]=1;
    for(it=G[p].begin();it!=G[p].end();it++)
        if(!uz[*it])
            DFS(*it);}