Puiut14id
a fost răspuns

#579 Drum Hamiltonian de pe pbinfo
VA ROGGG!!!!

Cerința


Se dă un graf orientat cu n noduri. Determinați, dacă există, un drum hamiltonian – drum elementar care conține toate nodurile.


Date de intrare


Fișierul de intrare drum_hamiltonian.in conține pe prima linie numărul n, iar pe a următoarele linii perechi de numere i j, cu semnificația că există arc de la i la j.


Date de ieșire


Fișierul de ieșire drum_hamiltonian.out va conține pe prima linie numărul 1, dacă s-a determinat un drum hamiltonian, respect nu 0, în caz contrar. Dacă s-a determinat un drum hamiltonian, pe linia următoare se vor afișa nodurile acestui drum, separate prin exact un spațiu.


Restricții și precizări

1 ≤ n ≤ 10

1 ≤ i,j ≤ n

orice drum hamiltonian afișat corect va fi acceptat


Exemplu


drum_hamiltonian.in


5

1 5

2 1

2 5

3 1

4 2

5 3


drum_hamiltonian.out


1

4 2 1 5 3

Răspuns :

Coroană pls?

#include <fstream>

using namespace std;

ifstream f_in("drum_hamiltonian.in");

ofstream f_out("drum_hamiltonian.out");

int main()

{

bool matr_ad[11][11] = { 0 };

int noduri;

f_in >> noduri;

int nodX, nodY;

while (f_in >> nodX >> nodY)

 matr_ad[nodX][nodY] = 1;

int backtrack = 2;

int soluție[11] = { 0, 1 };

bool noduri_vizitate[11] = { 0 };

noduri_vizitate[1] = 1;

while (backtrack) {

 if (backtrack == noduri + 1) {

  for (int index = 1; index <= noduri; index++)

   f_out << soluție[index] << ' ';

  return 0;

 }

 else {

   if (soluție[backtrack] <= noduri) {

   soluție[backtrack]++;

   if (matr_ad[soluție[backtrack - 1]][soluție[backtrack]] && !noduri_vizitate[soluție[backtrack]]) {

    noduri_vizitate[soluție[backtrack]] = 1;

    backtrack++;

   }

  }

  else {

   soluție[backtrack] = 0;

   if (backtrack == 2) {

    noduri_vizitate[soluție[1]] = 0;

    soluție[1]++;

    noduri_vizitate[soluție[1]] = 1;

   }

   else

    backtrack--;

   noduri_vizitate[soluție[backtrack]] = 0;

  }

 }

}

f_out << 0;

return 0;

}