Cod sursa(job #915282)

Utilizator razvan9310FMI - Razvan Damachi razvan9310 Data 14 martie 2013 21:31:01
Problema Ciclu Eulerian Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
using namespace std;

void DepthFirstSearch(int vertex, vector<int> *&Graph, vector<int> &cycle)
{
	int i, j;
	for (i=0; i<Graph[vertex].size(); ++i)
	{
		int adjancted = Graph[vertex][i];

		for (j=0; Graph[adjancted][j] != vertex; ++j);
		Graph[adjancted][j] = Graph[adjancted][Graph[adjancted].size()-1];
		Graph[adjancted].pop_back();

		Graph[vertex][i] = Graph[vertex][Graph[vertex].size()-1];
		Graph[vertex].pop_back();
		--i;

        if (Graph[adjancted].size())
        {
            cycle.push_back(adjancted);
            cycle.push_back(vertex);
        }

		DepthFirstSearch(adjancted, Graph, cycle);
	}
}

bool hasEdges(vector<int> *G, int N)
{
    for (int i=1; i<=N; ++i)
        if (G[i].size())
            return 1;
    return 0;
}

int main()
{
	ifstream in("ciclueuler.in");
	ofstream out("ciclueuler.out");

	int N, M, i, a, b;
	vector<int> *Graph, cycle;

	in>>N>>M;
	Graph = new vector<int>[N+1];
	for (i=0; i<M; ++i)
	{
		in>>a>>b;
		Graph[a].push_back(b);
		Graph[b].push_back(a);
	}

	DepthFirstSearch(1, Graph, cycle);

    if (hasEdges(Graph, N))
    {
        out<<-1;
        return 0;
    }

	vector<int>::iterator it=cycle.begin(), stop=cycle.end();
	while (it != stop)
	{
		out<<*it<<" ";
		++it;
	}
	return 0;
}