Cod sursa(job #917131)

Utilizator dariusdariusMarian Darius dariusdarius Data 17 martie 2013 12:57:57
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<stdio.h>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
vector<int> sol,G[100005];
stack<int> st;
int viz[100005];
int n,deg[100005];
inline bool good()
{
    for(int i=1;i<=n;i++)
        if(deg[i]&1)
            return false;
    queue<int> q;
    q.push(1);viz[1]=1;
    while(!q.empty())
    {
        int nod=q.front();
        for(vector<int>::iterator it=G[nod].begin();it!=G[nod].end();it++)
            if(!viz[*it])
                viz[*it]=1,q.push(*it);
        q.pop();
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            return false;
    return true;
}
void euler(int nod)
{
    int next;
    while(!G[nod].empty())
    {
        next=G[nod].back();
        st.push(nod);
        G[nod].pop_back();
        for(vector<int>::iterator it=G[next].begin();it!=G[next].end();it++)
            if(*it==nod)
            {
                G[next].erase(it);
                break;
            }
        nod=next;
    }
}
int main()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    int m,i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        deg[x]++;G[x].push_back(y);
        deg[y]++;G[y].push_back(x);
    }
    if(!good())
    {
        printf("-1\n");
        return 0;
    }
    int nod=1;
    do
    {
        euler(nod);
        nod=st.top();st.pop();
        sol.push_back(nod);
    }while(!st.empty());
    for(vector<int>::iterator it=sol.begin();it!=sol.end();it++)
        printf("%d ",*it);
    printf("\n");
    return 0;
}