fork(9) download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <limits.h>
  4.  
  5. #define V 4
  6.  
  7. typedef enum { false, true } bool;
  8.  
  9. struct Queue
  10. {
  11.     int front, rear, capacity;
  12.     int* array;
  13. };
  14.  
  15. struct Queue* createQueue(int capacity)
  16. {
  17.     struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
  18.  
  19.     queue->capacity = capacity;
  20.     queue->front = queue->rear = -1;
  21.  
  22.     queue->array = (int*) malloc(queue->capacity * (sizeof(int)));
  23.  
  24.     return queue;
  25. }
  26.  
  27. bool isEmpty(struct Queue* queue)
  28. {
  29.     return queue->front == -1 ? true : false;
  30. }
  31.  
  32. bool isFull(struct Queue* queue)
  33. {
  34.     return queue->rear == queue->capacity - 1 ? true : false;
  35. }
  36.  
  37. void enQueue(struct Queue* queue, int item)
  38. {
  39.     if (isFull(queue))
  40.         return;
  41.  
  42.     queue->array[++queue->rear] = item;
  43.     if (isEmpty(queue))
  44.         ++queue->front;
  45. }
  46.  
  47. int deQueue(struct Queue* queue)
  48. {
  49.     if (isEmpty(queue))
  50.         return INT_MIN;
  51.  
  52.     int item = queue->array[queue->front];
  53.  
  54.     if (queue->front == queue->rear)
  55.         queue->front = queue->rear = -1;
  56.  
  57.     else
  58.         ++queue->front;
  59.  
  60.     return item;
  61. }
  62.  
  63. int initColorMatrix(int color[], int N)
  64. {
  65.     int i;
  66.     for (i = 0; i < N; ++i)
  67.         color[i] = -1;
  68. }
  69.  
  70. bool isBipartite(int G[][V], int src)
  71. {
  72.     int colorMatrix[V], color, temp, u;
  73.  
  74.     initColorMatrix(colorMatrix, V);
  75.  
  76.     struct Queue* queue = createQueue(V);
  77.  
  78.     color = 1;
  79.     colorMatrix[src] = color;
  80.     enQueue(queue, src);
  81.  
  82.     while (!isEmpty(queue))
  83.     {
  84.         temp = deQueue(queue);
  85.         // assign alternate color to its neighbor
  86.         color = 1 - colorMatrix[temp];
  87.  
  88.     	for (u = 0; u < V; ++u)
  89.         {
  90.         	// an edge exists and destination not colored
  91.         	if (G[temp][u] && colorMatrix[u] == -1)
  92. 	        {
  93. 		        colorMatrix[u] = color;
  94.                 enQueue(queue, u);
  95. 	        }
  96.  
  97.             else if (G[temp][u] && colorMatrix[u] == colorMatrix[temp])
  98.                 return false; 
  99.         }
  100.     }
  101.  
  102.     return true;
  103. }
  104.  
  105. int main()
  106. {
  107.     int G[][V] = {{0, 1, 0, 1},
  108.                   {1, 0, 1, 0},
  109.                   {0, 1, 0, 1},
  110.                   {1, 0, 1, 0}};
  111.  
  112.     isBipartite(G, 0) ? printf("Yes") : printf("No");
  113.  
  114.     return 0;
  115. }
Success #stdin #stdout 0s 1964KB
comments (?)
stdin 
Standard input is empty
stdout 
Yes
https://ideone.com/3VE7oj
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

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!