Cod sursa(job #1131819)

Utilizator costyv87Vlad Costin costyv87 Data 1 martie 2014 17:09:25
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.09 kb
#include <cstdio>
#include <vector>
#include <string>
#include <list>
#include <bitset>
#include <fstream>
#include <queue>
#include <stack>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=(st);i<=(dr);i+=(k))
#define ll (long long)
#define kfl(i,j) (a[(i)][(j)].c-a[(i)][(j)].f)
using namespace std;
FILE *f,*g;
list <int> a[100100];
bool bf[100100];
int gr[100100];
stack <int> S;
vector <int> sol;
int n,m;

void read()
{
    int i,x,y;

    f=fopen("ciclueuler.in","r");
    g=fopen("ciclueuler.out","w");

    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
}

void df(int x)
{
    bf[x]=true;
    for (list<int>::iterator i=a[x].begin();i!=a[x].end();i++) if (!bf[*i]) df(*i);
}

void bfs(int x)
{
    queue <int> q;

    q.push(x);
    bf[x]=true;
    while (q.size())
    {
        x=q.front(); q.pop();
        for (list <int>::iterator i=a[x].begin();i!=a[x].end();i++)
            if (!bf[*i])
            {
                bf[*i]=true;
                q.push(*i);
            }
    }
}

bool pre()
{
    bfs(1);
    for (int i=1;i<=n;i++) if (!bf[i] || gr[i]%2==1) return false;
    return true;
}

void euler(int x)
{
    int y;


    while (!a[x].empty())
    {
        y=a[x].front();
        a[x].pop_front();
        for (list<int>::iterator j =a[y].begin();j!=a[y].end();j++)
            if (*j==x)
            {
                a[y].erase(j);
                break;
            }

        S.push(x);
        x=y;
    }
}

void solve()
{
    int x=1;

    do
    {
        euler(x);
        x=S.top(); S.pop();
        sol.push_back(x);
    }
    while (S.size());
    for (int i=0;i<sol.size();i++) fprintf(g,"%d ",sol[i]);
}


int main()
{
    read();
    if (!pre()) { fprintf(g,"-1"); return 0;}
    solve();

    return 0;
}