Advertisement
tachia

Untitled

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