Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- bool hasHamiltonCycle(Grid<bool>& grapuka) {
- if(grapuka.size()==1|| grapuka.size()==0 || grapuka.size()==2){
- return false;
- }
- for(int i=0; i<grapuka.numCols(); i++){
- Set<int> sastavi;
- sastavi.add(i);
- int hamilton=0;
- checkForHamilton(grapuka,sastavi,i,i,hamilton);
- if(hamilton>=1){
- return true;
- }else{
- return false;
- }
- }
- }
- void checkForHamilton(Grid<bool>& grapuka,Set<int> sastavi,int first,int last,int &hamilton){
- if(sastavi.contains(last) && sastavi.size()>=2 && first==last){
- hamilton++;
- return;
- }
- if(sastavi.contains(last)&& sastavi.size()>=2){
- return;
- }
- for(int i=0; i<grapuka.numCols(); i++){
- if(grapuka[last][i]){
- Set<int> tavisi=sastavi;
- tavisi.add(grapuka[last][i]);
- checkForHamilton(grapuka,tavisi,first,grapuka[last][i],hamilton);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement