// Circuit Hamiltonien par backtracking #include using namespace std; void printSolution(const vector &); bool isSafe(const int v, const vector> &graph, const vector &path) { // Vérifier si v est voisin direct du dernier sommet ajouté au chemin : int last = path.back(); if(graph[last][v] == false) return false; // Vérifier si v a déjà été ajouté au chemin : return find(path.begin(), path.end(), v) == path.end(); // true si pas là } // isSafe() // Fonction de backtracking pour chercher un circuit Hamiltonien : bool hamCycleUtil(const vector> &graph, vector &path) { int V = graph.size(); // Cas de base : tous les sommets sont dans le chemin Hamiltonien, c'est gagné if(graph.size() == path.size()) { // Reste à vérifier si le premier et dernier sommet sont voisins int last = path.back(); return graph[last][path[0]] == true; } // On essaye chaque sommet v comme prochain sommet dans le chemin Hamiltonien : for(int v = 1; v < V; v++) { // Vérifier si on peut ajouter v comme prochain sommet dans le chemin : if(isSafe(v, graph, path)) // ok { path.push_back(v); // Appel récursif pour le prochain sommet : if(hamCycleUtil(graph, path) == true) return true; // Sinon : BACKTRACK path.pop_back(); } } return false; } // hamCycleUtil() bool hamCycle(const vector> &graph) { vector path; // chemin vide path.push_back(0); if(hamCycleUtil(graph, path) == false ) { cout << "Impossible\n"; return false; } else { printSolution(path); return true; } } // hamCycle() void printSolution(const vector &path) { for(int v : path) cout << v << ' '; cout << path[0] << '\n'; } // printSolution() // Programme principal int main() { int V = 0; cin >> V; // nombre de sommets vector> graphe(V, vector(V, false)); int x = 0; for(int i = 0; i < V; i++) for(int j = 0; j < V; j++) { cin >> x; if(x == 1) graphe[i][j] = true; } hamCycle(graphe); return 0; } //main()