Cod sursa(job #953671)

Utilizator blechereyalBlecher Eyal blechereyal Data 26 mai 2013 22:34:25
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>
#include <vector>
#include <stack>


using namespace std;
ifstream in("ciclueuler.in");
ofstream out("ciclueuler.out");
int N,M,x,y,*visited,*deg;
vector<int> *graph;
stack<int> S;
void del (int a,int b)
{
    deg[a]--;deg[b]--;
    vector<int>::iterator it;
    graph[a].erase(graph[a].begin());
    for (it=graph[b].begin();it!=graph[b].end();it++)
    if (*it==a) {graph[b].erase(it);break;}
}
void DFS(int node)
{
    visited[node]=1;
    vector<int>::iterator it;
    for (it=graph[node].begin();it!=graph[node].end();it++)
     if (visited[*it]==0) DFS(*it);
}

bool conex()
{
    int i;
    DFS(1);
    for (i=1;i<=N;i++)
    if (visited[i]==0) return false;
    return true;
}
bool deg_par()
{
    int i;
    for (i=1;i<=N;i++)
        if (deg[i]%2==1) return false;
    return true;
}
void euler(int node)
{   int w;
    while (!graph[node].empty())
    {
        w=*(graph[node].begin());
        S.push(node);
        del(node,w);
        node=w;
    }

}
int main()
{
    in>>N>>M;
    int i;
    graph=new vector<int> [N+2];
    visited=new int [N+2];
    deg=new int [N+2];
    for (i=1;i<=N;i++) visited[i]=0,deg[i]=0;
    for (i=1;i<=M;i++)
    {
        in>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
        deg[x]++;deg[y]++;
    }
    int s_node=1;
    if (conex() && deg_par())
    {while (!S.empty())
    {
        euler(s_node);
        s_node=S.top();
        S.pop();
        out<<s_node<<" ";
    }


    }

    else out<<"-1";
    return 0;
}