Cod sursa(job #1242781)

Utilizator cojocarugabiReality cojocarugabi Data 14 octombrie 2014 23:54:33
Problema Ciclu Eulerian Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
# include <bits/stdc++.h>
#define p(x) int(S[x].size())
using namespace std;
ifstream fi("ciclueuler.in");
ofstream fo("ciclueuler.out");
const int nmax = 100010;
stack < int > s;
vector < int > S[nmax];
int Sol[nmax],n;
bool b[nmax];
queue < int > q;
bool bfs()
{
    q.push(1);b[1]=1;
    while (q.size())
    {
        int v=q.back();q.pop();
        for (int i=0,j=p(v);i<j;++i) if (!b[S[v][i]]) q.push(S[v][i]),b[S[v][i]]=1;
    }
    for (int i=1;i<=n;++i) if (!b[i]) return 0;
    return 1;
}
bool eulerian()
{
    for (int i=1;i<=n;++i) if (p(i) & 1) return 0;
    return bfs();
}
int main(void)
{
    int m;
    fi>>n>>m;
    int x,y;
    while (m--) fi>>x>>y,S[x].push_back(y),S[y].push_back(x);
    if (!eulerian()) return fo<<"-1\n",0;
    s.push(1);
    while (s.size())
    {
        int v=s.top();
        if (!p(v)) Sol[++Sol[0]]=v,s.pop();
        else
        {
            int to=S[v][p(v)-1];
            s.push(to);
            S[v].pop_back();
            S[to].erase(find(S[to].begin(),S[to].end(),v));
        }
    }
    for (int i=1;i<Sol[0];++i) fo << Sol[i] << ' ';
    return 0;
}