Cod sursa(job #761933)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 27 iunie 2012 21:05:51
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.11 kb
#include <fstream>
#include <list>
#include <stack>
#include <queue>

#define MAX 100050

using namespace std;

list<int> E[MAX], L;
queue<int> Q; stack<int> S;
int grad[MAX], n, m;
char rd[200];
bool visited[MAX];

inline void citire()
{
    ifstream in("ciclueuler.in");
    in>>n>>m; in.get(); int a, b, i;
    for(;m;m--)
    {
        in.getline(rd, 200);
        a = 0; b = 0;
        for(i = 0; rd[i] != ' '; i++)
            a = a * 10 + rd[i] - '0';
        for(++i; rd[i] != '\0'; i++)
            b = b * 10 + rd[i] - '0';
        E[a].push_back(b);grad[a]++;
        E[b].push_back(a);grad[b]++;
    }
    in.close();
}

void bfs(int nod)
{
    Q.push(nod);
    while(!Q.empty())
    {
        int v = Q.front(); Q.pop();
        for(list<int>::iterator it = E[v].begin(); it != E[v].end(); it++)
        if(!visited[*it])
        {
            visited[*it] = true;
            Q.push(*it);
        }
    }
}

bool isEulerian()
{
    visited[1] = true; bfs(1);
    for(int i = 1; i <= n; i++)
        if(!visited[i] || (grad[i] & 1))
            return false;
    return true;
}

void sterge(int v, int w)
{
    grad[v]--;grad[w]--;
    E[v].pop_front();
    for(list<int>::iterator it = E[w].begin(); it != E[w].end(); it++)
        if((*it) == v)
        {
            E[w].erase(it);
            return;
        }
}

void euler(int nod)
{
    while(!E[nod].empty())
    {
        int v = E[nod].front();
        S.push(nod);
        sterge(nod, v);
        nod = v;
    }
}

inline int solve()
{
    if(!isEulerian())
        return -1;
    else
    {
        int v = 1;
        do
        {
            euler(v);
            v = S.top(); S.pop();
            L.push_back(v);
        }while(!S.empty());
        return 10;
    }
}

void afisare(int ok)
{
    ofstream out("ciclueuler.out");
    if(ok == -1)
        out<<"-1";
    else
    {
        for(list<int>::iterator it = L.begin(); it != L.end(); it++)
            out<<(*it)<<" ";
    }
    out.close();
}

int main()
{
    citire();
    afisare(solve());
    return 0;
}