Cod sursa(job #1881659)

Utilizator FlowstaticBejan Irina Flowstatic Data 16 februarie 2017 17:29:00
Problema Ciclu Eulerian Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#define NMAX 100005

using namespace std;
FILE* fin = fopen("ciclueuler.in","r");
FILE* fout = fopen("ciclueuler.out","w");

vector<int> G[NMAX];
stack<int> stiv;
int N,M;
int viz[NMAX];

void DFS(int x)
{
    viz[x] = 1;
    for(int i = 0; i<G[x].size();i++)
        if(!viz[G[x][i]])
            DFS(G[x][i]);
}

bool VerificaEulerian()
{
    DFS(1);
    for(int i = 1;i<=N;i++)
        if(!viz[i] || G[i].size() %2 == 1)
            return false;

    return true;

}

int main()
{
    fscanf(fin,"%d %d",&N,&M);
    int x,y;
    while(M--)
    {
        fscanf(fin,"%d %d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    if(VerificaEulerian())
    {
        int vf = 1,vf2;
        stiv.push(vf);

        while(!stiv.empty())
        {
            vf = stiv.top();
            if(G[vf].size() == 0)
            {
                fprintf(fout,"%d ",vf), stiv.pop();
            }
            else
            {
                vf2 = G[vf][G[vf].size()-1];
                stiv.push(vf2);
                G[vf].pop_back();
                G[vf2].erase(find(G[vf2].begin(),G[vf2].end(), vf));
            }
        }

    }
    else
            fprintf(fout,"-1\n");
    return 0;
}