Cod sursa(job #1369765)

Utilizator vlady1997Vlad Bucur vlady1997 Data 3 martie 2015 11:14:23
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
        #include <cstdio>
        #include <vector>
        #include <list>
        using namespace std;
        vector <int> g[100001];
        vector <int> :: iterator it;
        list <int> q;
        bool ok=false;
        void afis (void)
        {
            while (!q.empty())
            {
                if (q.size()!=1) printf("%d ",q.front());
                q.pop_front();
            }
            ok=true;
        }
        void euler (int x)
        {
            int i; q.push_back(x);
            if (q.front()==q.back() && q.size()>1)
            {
                afis();
                return;
            }
            while (!g[x].empty())
            {
                int y=g[x].back();
                g[x].pop_back();
                for (it=g[y].begin(); it!=g[y].end(); it++)
                {
                    if (*it==x)
                    {
                        g[y].erase(it);
                        break;
                    }
                }
                euler(y);
                q.pop_back();
            }
        }
        int main()
        {
            int n, m, x, y, i;
            freopen("ciclueuler.in","r",stdin);
            freopen("ciclueuler.out","w",stdout);
            scanf("%d%d",&n,&m);
            for (i=1; i<=m; i++)
            {
                scanf("%d%d",&x,&y);
                g[x].push_back(y);
                g[y].push_back(x);
            }
            for (i=1; i<=n; i++)
            {
                if (g[x].size()%2!=0)
                {
                    printf("-1");
                    return 0;
                }
            }
            for (i=1; i<=n; i++)
            {
                if (g[i].size()>0)
                {
                    q.clear();
                    euler(i);
                }
                if (ok==true) return 0;
            }
            return 0;
        }