fork download
copy 
  1. #include <iostream>
  2. #define FIN "graph.in"
  3. #define SIZE 50
  4.  
  5. using namespace std;
  6.  
  7. int mat[SIZE][SIZE], stack[SIZE],
  8. nodes,
  9. k,
  10. start_node;
  11.  
  12. void loadGraph() {
  13.     int i, j;
  14.     //freopen(FIN, "r",stdin);
  15.      //citim numarul de noduri
  16.      cin>>nodes;
  17.  
  18.      //citim muchiile (i,j)
  19.      //de la i la j si de la j la i
  20.      while(cin>>i>>j) {
  21.        mat[i][j] = 1;
  22.        mat[j][i] = 1;
  23.      }
  24. }
  25.  
  26. void displayGraph() {
  27.  
  28.      for(int i = 1; i <= nodes; i++) {
  29.         for(int j = 1; j <= nodes; ++j) {
  30.           printf("%d ", mat[i][j]);
  31.         }
  32.  
  33.         printf("\n");
  34.      }
  35. }
  36.  
  37. void init() {
  38.     //k = 2; stack[2] = 0
  39.     stack[ k ] = 0;
  40. }
  41.  
  42. int succ() {
  43.  
  44.     if(stack[k] < nodes) {//0 < 9 ?
  45.  
  46.        stack[k]++;//stack[k] = 1 + 1 = 2 (varful) stack[k] = 2
  47.        return 1;
  48.     }
  49.     return 0;
  50. }
  51.  
  52. int valid() {
  53.  
  54.     if(!mat[ stack[k-1] ] [ stack[k] ]) return 0;
  55.  
  56.     for(int i = 1; i < k ; ++i)
  57.  
  58.            if(stack[i] == stack[k]) return 0;
  59.  
  60.     return 1;
  61. }
  62.  
  63. int sol() {
  64.  
  65.     return (k == nodes) && (mat[ start_node ][ stack[k] ] == 1);
  66. }
  67.  
  68. void display_solution() {
  69.  
  70.      for(int i = 1; i <= nodes; ++i) printf("%d ", stack[i]);
  71.  
  72.      printf("%d", start_node);
  73.      printf("\n");
  74. }
  75.  
  76. //backtracking iterative
  77. void bkt() {
  78.  
  79.      int h, v;
  80.  
  81.      k = 2;
  82.  
  83.      init();
  84.  
  85.      while(k > 1) {
  86.  
  87.            h = 1;
  88.            v = 0;
  89.            while(h && !v) {
  90.                h = succ();
  91.                if(h) v = valid();
  92.            }
  93.  
  94.            if(h) {
  95.  
  96.              if(sol()) {
  97.                 display_solution();
  98.                 //k = 1;
  99.              } else {
  100.                k++;init();
  101.              }
  102.  
  103.            } else k--;
  104.      }
  105.  
  106. }
  107.  
  108. int main(int argc, char const *argv[]) {
  109.  
  110.   printf("%s","Nodul de start = ");
  111.   scanf("%d", &start_node);
  112.  
  113.   loadGraph();
  114.   printf("%s\n", "Graful neorientat");
  115.   displayGraph();
  116.  
  117.   stack[1] = start_node;
  118.   //k = 2;
  119.   //stack[2] = 1;
  120.  
  121.   printf("%s\n","Drumuri hamiltoniene:");
  122.   bkt();
  123.  
  124.   return 0;
  125. }
  126.  
  127. //k=3; stack[k] :3
  128. //k=2; stack[k] :2
  129.                 //muchie
  130. //k=1; stack[k] :1 (varf)
  131.  
  132. //stack[k] = Varf
  133.  
  134. //node_start = 5
  135.  
  136. //stack[1] = 5
  137.  
  138.              //init()
  139. //stack[2] = stack[2] + 1 = 0 + 1 = 1
  140.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
9
1 2
1 4
2 3
2 4
2 5
3 4
3 8
3 9
4 6
5 6
5 7
5 8
7 8
8 9
stdout
copy 
Nodul de start = Graful neorientat
0 1 0 1 0 0 0 0 0 
1 0 1 1 1 0 0 0 0 
0 1 0 1 0 0 0 1 1 
1 1 1 0 0 1 0 0 0 
0 1 0 0 0 1 1 1 0 
0 0 0 1 1 0 0 0 0 
0 0 0 0 1 0 0 1 0 
0 0 1 0 1 0 1 0 1 
0 0 1 0 0 0 0 1 0 
Drumuri hamiltoniene:
5 6 4 1 2 3 9 8 7 5
5 7 8 9 3 2 1 4 6 5
https://ideone.com/8zomIJ
Hamiltonian Graph
language:
C++ (gcc 8.3)
created:
257 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!