fork download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #define MAX 50
  4.  
  5. struct Node {
  6.  
  7.        int info;
  8.        struct Node *next;
  9. };
  10.  
  11. struct Node *head, *ind, *c;
  12.  
  13. void readGraph(const char*);
  14. void displayMatrix();
  15. int connex();
  16. int have_degree();
  17. void dfs(int);
  18. int add();
  19. void cycle(struct Node *);
  20.  
  21. int mat[MAX][MAX], visited[ MAX ];
  22.  
  23. int num_vertices, num_edges;
  24.  
  25. FILE *fin, *fout;
  26.  
  27. //main program
  28. int main() {
  29.  
  30.     readGraph("eulerian.in");
  31.  
  32.     if( connex() ) {
  33.  
  34.           if( have_degree() ) {
  35.  
  36.              head = (struct Node*)malloc(sizeof(struct Node));
  37.              head->info = 1;
  38.              head->next = 0;
  39.  
  40.              while( add() );
  41.  
  42.              c = head;
  43.              while( c ) {
  44.                    printf("%d ", c->info);
  45.                    c = c->next;
  46.              }
  47.  
  48.           } else {
  49.  
  50.            printf("The Graph does n respect the conditions for parity");
  51.  
  52.           }
  53.  
  54.     } else {
  55.  
  56.            printf("The Graph is not connex");
  57.     }
  58.  
  59.     return(0);
  60. };
  61.  
  62. //@param filename from where we can read the graph onto matrix of adjacence
  63. //@return Void.
  64. void readGraph(const char *filename) {
  65.  
  66.      int i,j;
  67.  
  68.      scanf("%d %d", &num_vertices, &num_edges);
  69.  
  70.      for(;num_edges; num_edges--) {
  71.  
  72.           scanf("%d %d",&i,&j);
  73.           mat[i][j] = mat[j][i] = 1;
  74.      }
  75.  
  76. }
  77.  
  78. //display the matrix adjacence for debug
  79. //@param void
  80. //@return void
  81. void displayMatrix() {
  82.  
  83.      int i,j;
  84.  
  85.      for(i=1;i<=num_vertices;i++) {
  86.  
  87.          for(j=1;j<=num_vertices;j++) {
  88.  
  89.              printf("%d ", mat[i][j]);
  90.          }
  91.              printf("\n");
  92.      }
  93. }
  94.  
  95. //chech if the graph is odd or not
  96. int have_degree() {
  97.  
  98.     int sum,i,j,not = 1;
  99.  
  100.     for(i = 1; i <= num_vertices; i++) {
  101.  
  102.         sum = 0;
  103.  
  104.         for(j = 1; j <= num_vertices; j++) {
  105.  
  106.             sum += mat[i][j];
  107.         }
  108.  
  109.         if(sum&1) not = 0;
  110.  
  111.         if(!not) return not;
  112.     }
  113.     return not;
  114. }
  115.  
  116. //check whether the graph is connex or not
  117. int connex() {
  118.     int i;
  119.  
  120.     dfs(1);
  121.  
  122.     for(i=1;i<=num_vertices;i++)
  123.  
  124.         if(!visited[i])
  125.  
  126.             return 0;
  127.  
  128.     return 1;
  129. }
  130.  
  131. //Depth First Search Traversal
  132. void dfs(int node) {
  133.  
  134.      int j;
  135.  
  136.      visited[ node ] = 1;
  137.  
  138.      for(j = 1; j <= num_vertices; j++) {
  139.  
  140.          if(mat[ node ][ j ]) {
  141.  
  142.                 if(!visited[ j ]) {
  143.  
  144.                     dfs( j );
  145.                 }
  146.          }
  147.      }
  148. }
  149.  
  150. int add() {
  151.  
  152.     int node, i, found = 0;
  153.  
  154.     struct Node *ind;
  155.  
  156.     ind = head;
  157.  
  158.     while(ind && !found) {
  159.  
  160.           for(i = 1; i <= num_vertices; i++) {
  161.  
  162.               if(mat[ind->info][ i ] == 1) found = 1;
  163.           }
  164.  
  165.           if( !found ) ind = ind->next;
  166.     }
  167.  
  168.  
  169.     if( ind ) {
  170.  
  171.        cycle( ind );
  172.  
  173.        return 1;
  174.     }
  175.  
  176.     return 0;
  177. };
  178.  
  179. void cycle(struct Node *p) {
  180.  
  181.      struct Node *newnode, *nextnode, *basenode;
  182.  
  183.      int node;
  184.  
  185.      basenode = p;
  186.      nextnode = p->next;
  187.  
  188.      do{
  189.      node = 1;
  190.  
  191.      while(mat[ basenode->info ][ node ] == 0) node++;
  192.  
  193.      mat[basenode->info][ node ] = 0;
  194.      mat[ node ][ basenode->info ] = 0;
  195.  
  196.      newnode = (struct Node*)malloc(sizeof(struct Node));
  197.      newnode->info = node;
  198.      newnode->next = NULL;
  199.  
  200.      basenode->next = newnode;
  201.      basenode = newnode;
  202.      }while(newnode->info != p->info);
  203.  
  204.      basenode->next = nextnode;
  205. };
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
9 14
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 
1 2 4 6 5 7 8 3 9 8 5 2 3 4 1
https://ideone.com/xPPdxU
Eulerian Path
language:
C (gcc 8.3)
created:
282 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!