C   473

Hamiltonian

Guest on 31st May 2022 05:25:46 PM

  1. /*
  2. Author: Varun Kakathiya
  3. Created: 10:55:35 PM, Tuesday 31, May 2022
  4. Contest: -
  5. Problem: Hamiltonian Cycle
  6. */
  7.  
  8. #include <stdio.h>
  9. #include<stdbool.h>
  10. int g[10][10];
  11. int x[10];
  12. int flag=0;
  13. int n,start;
  14. void hamiltonian(int k)
  15. {
  16.     x[1]=start;
  17.     do
  18.     {
  19.         nextvalue(k);
  20.         if( x[k] == 0) return;
  21.         if(k==n)
  22.         {
  23.             flag=1;
  24.             for(int i=1;i<=n;i++)
  25.             printf("%d    ",x[i]);
  26.               printf("\n");
  27.         }
  28.         else
  29.         hamiltonian(k+1);
  30.     }
  31.     while(true);
  32. }
  33. void nextvalue(int k)
  34. {
  35.     int j=0;
  36.     do{
  37.         x[k]=(x[k]+1)%(n+1);
  38.         if(x[k]==0) return;
  39.         if(g[x[k-1]][x[k]]==1)
  40.         {
  41.             for(j=1;j<=k-1;j++)
  42.                 if(x[j]==x[k]) break;
  43.                 if(j==k)
  44.                     if(  k<n || ((k==n) && g[x[n]][x[1]]==1))
  45.                      return;
  46.         }
  47.     }
  48.     while(true);
  49. }
  50.  
  51. int main() {
  52.  
  53.         scanf("%d",&n); //total no of vertices
  54.         for(int i=1;i<=n;i++)
  55.         {
  56.             for(int j=1;j<=n;j++)
  57.             scanf("%d",&g[i][j]);
  58.         }
  59. //      printf("Enter starting node\n");
  60.         scanf("%d",&start); //starting node
  61.         hamiltonian(2);
  62.         if(!flag)
  63.         printf("Hamilton  cycle does not exist\n");
  64.         return 0;
  65. }
  66.  
  67. /* INPUT:
  68.    6
  69. 0 1 1 0 0 1
  70. 1 0 1 0 0 1
  71. 1 1 0 1 0 0
  72. 0 0 1 0 1 0
  73. 0 0 0 1 0 1
  74. 1 1 0 0 1 0
  75. 1
  76.  
  77. OUTPUT:
  78. 1    2    3    4    5    6    
  79. 1    2    6    5    4    3    
  80. 1    3    4    5    6    2    
  81. 1    6    5    4    3    2  
  82.  
  83. */

Raw Paste


Login or Register to edit or fork this paste. It's free.