Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.6 kB
3
Indexable
Never

#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std;

#define NUMBER_OF_NODES 5 

// matricea de adiacenta 
vector<vector<int> > adj(NUMBER_OF_NODES, vector<int>(NUMBER_OF_NODES));

// vectorul vizitat sa tina cont de nodurile vizitate 
vector<int> visited(NUMBER_OF_NODES);

// functia de backtracking 
bool solve(int node, int n, int v, vector<int>& path)
{
	// adaugam nodul la parcurs 
	path.push_back(node);
	visited[node] = true;

	// daca toate nodurile au fost vizitate, 
	// si ultimul nod din ciclu se conecteaza la primul 
	// atunci am gasit ciclul 
	if (path.size() == n &&
		adj[node][path[0]] == 1)
		return true;

	// incercam toate nodurile nevizitate 
	for (int i = 1; i < n; i++)
	{
		if (adj[node][i] == 1 && !visited[i])
		{
			if (solve(i, n, v, path))
				return true;
			else
				path.pop_back();
		}
	}

	return false;
}

// driver 
int main()
{
	int v;
	cout << "Numarul de noduri: " << endl;
	cin >> v;

	// citirea perechilor de valori 
	int a, b;
	for (int i = 0; i < v; i++)
	{
		cout << " Introduceti perechea de valori " << i + 1 << ": ";
		cin >> a >> b;

		adj[a - 1][b - 1] = 1;
		adj[b - 1][a - 1] = 1;
	}

	// vectorul nodurilor 
	vector<int> path;

	// se incepe de la nodul 1 
	if (solve(1 - 1, v, v, path))
	{
		cout << "Ciclul Hamiltonian exista: " << endl;
		for (int i = 0; i < path.size(); i++)
			cout << path[i] + 1 << " ";

		cout << path[0] + 1;
	}
	else
		cout << "Ciclul Hamiltonian nu exista";

	return 0;
}

/*Numarul de noduri 5
	1 2
	2 5
	5 3
	3 4
	4 1
Alt ciclu hamiltonian
1-2, 2-3, 3-4, 4-5, 5-1
Ciclul Hamiltonian : 1 2 5 3 4 1
*/