Cod sursa(job #1754452)

Utilizator KronSabau Valeriu Kron Data 8 septembrie 2016 11:48:51
Problema Ciclu Eulerian Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.05 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <iterator>
#include <queue>
#include <stack>
using namespace std;
ifstream f("ciclueuler.in");
ofstream g("ciclueuler.out");
int n,m;
vector <int> adjList[100010];
queue <int> path;
stack <int> S;
queue <int> q;

int nrEdge[100010],visited[100010];

void Bfs()
{
    int v;
    q.push(1);
    visited[1]=1;
    while(!q.empty())
    {
        v=q.front();
        q.pop();
        for(vector<int>::iterator it=adjList[v].begin();it!=adjList[v].end();it++)
            if(visited[*it]==0)
            {
                visited[*it]=1;
                q.push(*it);
            }


    }

}

int check()
{
    Bfs();
    for(int i=1;i<=n;i++)
        if(visited[i]==0)
            return 0;
    for(int i=1;i<=n;i++)
        if(nrEdge[i]%2==1)
            return 0;

        return 1;
}


void deleteEgde(int v,int w)
{
    adjList[v].pop_back();
    for(vector<int>::iterator it=adjList[w].begin();it!=adjList[w].end();it++)
        if(*it==v)
        {
            adjList[w].erase(it);
            break;
        }

}

void EulerianCycle()
{
    int w,v;
    while(!S.empty()){
        v=S.top();S.pop();

        while(!adjList[v].empty())
        {
            w=adjList[v].back();
            deleteEgde(v,w);
            S.push(w);
            v=w;
        }
         path.push(v);

    }

}

void euler(int v)
{
    while(!adjList[v].empty())
    {
        int w=adjList[v].back();
        deleteEgde(v,w);
        euler(w);
    }
    path.push(v);
}

int main()
{
    f >> n >> m;
    int x,y;
    for(int i=0;i<m;i++){
        f >> x >> y;
        adjList[x].push_back(y); nrEdge[x]++;
        adjList[y].push_back(x); nrEdge[y]++;
    }
    if(check()==1){
        //S.push(1);
        //EulerianCycle();
       euler(1);
        path.pop();
        while(!path.empty())
        {
            g << path.front() << " ";
            path.pop();
        }


    }else g << "-1";
    return 0;
}