tachia

Untitled

Aug 28th, 2018
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. bool hasHamiltonCycle(Grid<bool>& grapuka) {
  2.         if(grapuka.numCols()==1|| grapuka.numCols==0 || grapuka.numCols==2){
  3.             return false;
  4.         }
  5.         int hamilton=0
  6.         for(int i=0; i<grapuka.numCols(); i++){
  7.             Set<int> sastavi;
  8.             sastavi.add(i);
  9.            
  10.             checkForHamilton(grapuka,sastavi,i,i,hamilton);
  11. if(hamilton>=1){
  12.                 return true;
  13.             }else{
  14.                 return false;
  15.             }
  16.            
  17.         }  
  18.        
  19.     }
  20.     void checkForHamilton(Grid<bool>& grapuka,Set<int> sastavi,int first,int last,int &hamilton){
  21.         if(sastavi.contains(last) && sastavi.size()>=2 && first==last){
  22.             hamilton++;
  23.             return;
  24.         }
  25.         if(sastavi.contains(last)&& sastavi.size()>=2){
  26.             return;
  27.         }
  28.         for(int i=0; i<grapuka.numCols(); i++){
  29.             if(grapuka[last][i]){
  30.                 Set<int> tavisi=sastavi;
  31.                 tavisi.add(grapuka[last][i]);
  32.                 checkForHamilton(grapuka,tavisi,first,grapuka[last][i],hamilton);
  33.             }
  34.            
  35.         }
  36.     }
Advertisement
Add Comment
Please, Sign In to add comment