Cod sursa(job #1586446)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 1 februarie 2016 10:46:50
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <iostream> //G este multigraf. Sa se det. daca G este eulerian.
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100005
#define MMAX 500005
using namespace std;
vector<int> V[NMAX], grad, C;
vector<bool> viz;
//vector<int> V[NMAX], C, grad;
stack<int> L;
int N, M, nodStart;

void citire()
{
    int u,v;
    scanf("%d%d", &N, &M);
    grad.assign(N+2, 0);

    for(int i=1; i<=M; i++)
    {
        scanf("%d %d", &u, &v);
        V[u].push_back(v);  grad[u]++;
        if(u!=v)
            V[v].push_back(u);
        grad[v]++;
    }
}
bool verificare()
{
    for(int i=1; i<=N; i++)
        if(grad[i] % 2 == 1)
            return 0;
        else if(!nodStart)
            nodStart=i;
    return 1;
}

void afisare()
{
    for(int i=0; i<C.size()-1; i++)
        cout<<C[i]<<' ';
    cout<<'\n';
}

void dfsIterativ(int nod)
{
    int nodStiva, vecin;
    L.push(nod);
    while(!L.empty())
    {
        nodStiva=L.top();
        L.pop();
        if(grad[nodStiva]){
            viz.assign(N+2, 0);
            for(int i=V[nodStiva].size()-1; i>=0; i--)
                if(V[nodStiva][i]!=0 && viz[V[nodStiva][i]]==0)
                {
                    vecin = V[nodStiva][i];
                    V[nodStiva][i]=0;
                    for(int j=0; j < V[vecin].size(); j++){
                        if(V[vecin][j]==nodStiva){
                            V[vecin][j]=0;
                            break;
                        }
                    }
                    grad[nodStiva]--;
                    grad[vecin]--;
                    //if(nodStiva != vecin)
                    L.push(vecin);
                    viz[vecin]=1;
                    //break;
                }
        }
        C.push_back(nodStiva);

    }
    afisare();
}

int main()
{
    freopen("ciclueuler.in", "rt", stdin);
    freopen("ciclueuler.out", "wt", stdout);
    citire();
    if(verificare()==0)
        cout<<"-1\n";
    else
        dfsIterativ(nodStart);



}