ulvis.paste.net

Paste Search Dynamic
Recent pastes
graph2
  1. #include <bits/stdc++.h>
  2. #define V 5
  3. using namespace std;
  4. bool hamil(bool graph[V][V],int pos,bool vis[V],int path[V])
  5. {
  6.         if(pos==V)
  7.         {
  8.                 if(graph[path[pos-1]][0])
  9.         return true;
  10.         else
  11.         return false;
  12.         }
  13.         for(int i=1;i<V;i++)
  14.         {
  15.                 if(vis[i]==0 && graph[path[pos-1]][i])
  16.                 {
  17.                         path[pos]=i;
  18.                         vis[i]=1;
  19.                         if(hamil(graph,pos+1,vis,path))
  20.                         return true;
  21.                         vis[i]=0;
  22.                         path[pos]=-1;
  23.                 }
  24.         }
  25.         return false;
  26. }
  27. int main() {
  28.         // your code goes here
  29.          bool graph1[V][V] = {{0, 1, 0, 1, 0},
  30.                       {1, 0, 1, 1, 1},
  31.                       {0, 1, 0, 0, 1},
  32.                       {1, 1, 0, 0, 1},
  33.                       {0, 1, 1, 1, 0},
  34.                      };
  35.  bool vis[V];
  36.  memset(vis,false,sizeof vis);
  37.  int path[V];
  38.  memset(path,-1,sizeof path);
  39.  path[0]=0;
  40.  vis[0]=1;
  41.  cout<<hamil(graph1,1,vis,path);
  42.     for (int i = 0; i < V; i++)
  43.         printf(" %d ", path[i]);
  44.  
  45.     // Let us print the first vertex again to show the complete cycle
  46.     printf(" %d ", path[0]);
  47.     printf("\n");
  48.       bool graph2[V][V] = {{0, 1, 0, 1, 0},
  49.                       {1, 0, 1, 1, 1},
  50.                       {0, 1, 0, 0, 1},
  51.                       {1, 1, 0, 0, 0},
  52.                       {0, 1, 1, 0, 0},
  53.                      };
  54.                       memset(vis,false,sizeof vis);
  55.  memset(path,-1,sizeof path);
  56.  path[0]=0;
  57.  vis[0]=1;
  58.                      cout<<hamil(graph2,1,vis,path);
  59.         return 0;
  60. }
Parsed in 0.012 seconds