Cod sursa(job #1212189)

Utilizator jul123Iulia Duta jul123 Data 24 iulie 2014 00:18:57
Problema Ciclu Eulerian Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include<iostream>
#include<cstdio>
#include<list>
#include<stack>
#include<vector>

using namespace std;

vector<int>g[100005];
vector<int> sol;
stack<int> s;
int n;
int gr[100005], viz[100005];

void DF(int v)
{
    viz[v]=1;
    for(int i=0; i<g[v].size(); i++)
    {
        if(viz[g[v][i]]==0)
            DF(g[v][i]);
    }
}
bool verific()
{
    DF(1);
    for(int i=1; i<=n; i++)
        if(viz[i]==0)
            return 0;
   for(int i=1; i<=n; i++)
        if(gr[i]%2==1)
            return 0;
    return 1;
}
void ciclu(int v)
{
    int w;
    while(!g[v].empty())
    {
        w=g[v].front();
        s.push(v);
        gr[v]--;
        gr[w]--;
        g[v].erase(g[v].begin());

        for(vector<int>::iterator it=g[w].begin(); it!=g[w].end(); it++)
        {
            if(*it==v) {
                g[w].erase(it);
                break;
            }
        }
        v=w;
    }
}
int main()
{
    FILE *fin, *fout;
    fin=fopen("ciclueuler.in", "r");
    fout=fopen("ciclueuler.out", "w");

    int x, y, m;
    fscanf(fin, "%d %d", &n, &m);
    for(int i=0; i<m; i++)
    {
        fscanf(fin, "%d %d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
        gr[x]++;
        gr[y]++;
    }
    if(verific()==0)
        fprintf(fout, "-1");
    else {
    int v=1;
    do{
        ciclu(v);
        v=s.top();
        s.pop();
        sol.push_back(v);
    }while(!s.empty());
    for(int i=0; i<sol.size(); i++)
    {
        fprintf(fout, "%d ", sol[i]);
    }
    }
}