Advertisement
Five_NT

[C++]Hamiltonian & ciucluri hamiltoniane

Jan 9th, 2014
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. int a[100][100], i, j, n, p, x[100], k;
  7.  
  8. void citire();
  9. int hemiltonian();
  10. void afis();
  11. int cont(int k);
  12. void back();
  13.  
  14. int main()
  15. {
  16.     citire();
  17.     if(hamiltonian())
  18.     {   cout<<"Este hamiltonian.";
  19.         back();
  20.     }
  21.     else cout<<"Nu este!";
  22.        
  23.         return 0;
  24. }
  25. int hamiltonian()
  26. {
  27.     // test
  28. }
  29. void citire()
  30. {
  31.     ifstream f("c.in");
  32.     f>>n;
  33.     for(int i=1; i<=n; i++)
  34.         for(int j=1; j<=n; j++)
  35.             f>>a[i][j];
  36.     f.close();
  37. }
  38.  
  39. int cont(int k)
  40. {
  41.     for(int i=1;i<k;i++)
  42.         if(x[i]==x[k])
  43.             return 0;
  44.         if(k>1)
  45.             if(a[x[k]][x[k-1]]==0)
  46.                 return 0;
  47.             if(k==n)
  48.                 if(a[x[n]][x[1]]==0)
  49.                     return 0;
  50.     return 1;
  51. }
  52. void afis()
  53. {
  54.     for(int i=1;i<=n;i++)
  55.         cout<<x[i]<<' ';
  56.     cout<<x[1];
  57.     cout<<endl;
  58. }
  59. void back()
  60. {
  61.     k=1;x[0]=0;
  62.     x[k]=x[k-1];
  63.     do
  64.     {
  65.         while(x[k]<n)
  66.         {
  67.             x[k]++;
  68.         if(cont(k))
  69.             if(k==n)
  70.                 afis();
  71.             else
  72.             {
  73.                 k++;
  74.                 x[k]=0;
  75.             }
  76.         }
  77.             k--;
  78.     }
  79.     while(k);
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement