Cod sursa(job #2072982)

Utilizator stefanchistefan chiper stefanchi Data 22 noiembrie 2017 16:07:45
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <bitset>
#include <vector>
#include <stack>
#define Nmax 100010
#define Mmax 500010
using namespace std;
vector<int > graf[Nmax];
bitset <Mmax> viz;
stack <int> varfuri;
int n,m;

struct muchie{
    int start,sfarsit;
}vec[Mmax];

void algorithm()
{
    varfuri.push(1);
    while(!varfuri.empty())
    {
        int nod = varfuri.top();
        if(!graf[nod].empty())
        {
            int vecin = graf[nod].back();
            graf[nod].pop_back();
            if(viz[vecin] == true)
                continue;
            viz[vecin] = true;
            if(vec[vecin].start == nod)
                varfuri.push(vec[vecin].sfarsit);
            else
                varfuri.push(vec[vecin].start);
        }
        else
        {
            printf("%d ", nod);
            varfuri.pop();
        }
    }

}



void read()
{
    freopen("ciclueuler.in","r",stdin);
    freopen("ciclueuler.out","w",stdout);
    scanf("%d %d",&n,&m);
    int x,y;
    for(int i =0 ; i < m ; i ++)
    {
        scanf("%d %d",&x,&y);
        vec[i].start = x;
        vec[i].sfarsit = y;
        graf[vec[i].start].push_back(i);
        graf[vec[i].sfarsit].push_back(i);
    }

    for(int i = 0 ; i < n ;i++)
        if(graf[i].size() % 2 == 1)
        {
            printf("-1");
            return;
        }
    algorithm();
}



int main()
{
    read();
    return 0;
}