Cod sursa(job #1619057)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 28 februarie 2016 11:59:28
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream ka("ciclueuler.in");
ofstream ki("ciclueuler.out");

const int N_MAX = 100000;
const int M_MAX = 500000;

struct muchie
{
    int index, id;
};

vector <muchie> graf[N_MAX + 1];
vector <int> sol;
stack <int> stiva;

bool folosita[M_MAX + 1];
int grad[N_MAX + 1], folosite;

int n, m, a, b;

int main()
{
    ka >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        ka >> a >> b;
        grad[a]++;
        grad[b]++;
        muchie mm;
        mm.index = b;
        mm.id = i;
        graf[a].push_back(mm);
        mm.index = a;
        graf[b].push_back(mm);
    }
    bool eulerian = true;
    for(int i = 1; i <= n && eulerian; i++)
        if(grad[i] % 2 == 1)
            eulerian = false;
    if(eulerian)
    {
        int curent = 1;
        while(curent < n && grad[curent] == 0)
 	      curent++;
        stiva.push(curent);
        while(!stiva.empty())
        {
            int t = stiva.top();
            while(!graf[t].empty() && folosita[graf[t].back().id])
                graf[t].pop_back();
            if(!graf[t].empty())
            {
                folosita[graf[t].back().id] = true;
                folosite++;
                stiva.push(graf[t].back().index);
                graf[t].pop_back();
            }
            else
            {
                if(stiva.size() != 1)
                    sol.push_back(t);
                stiva.pop();
            }
        }
    }
    if(folosite != m)
        eulerian = false;
    if(eulerian)
        for(int i = 0; i < sol.size(); i++)
            ki << sol[i] << " ";
    else
        ki << -1;
    return 0;
}