二分图判定

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum { UNKNOWN = 0, BLACK = 1, WHITE = 2 } Color;

typedef struct {
  int to;
  int next;
} Edge;

void addEdge(int* head, Edge* edges, int u, int v, int i) {
  (*(edges + i)).next = *(head + u);
  (*(edges + i)).to = v;
  *(head + u) = i;
}

void printAdjList(int* head, Edge* edges, const int n) {
  int i, u;
  for (u = 1; u <= n; ++u) {
    fprintf(stdout, "vertex %d: [ ", u);
    for (i = *(head + u); i; i = (*(edges + i)).next)
      fprintf(stdout, "%d ", (*(edges + i)).to);
    fputs("]\n", stdout);
  }
  fputc(10, stdout);
}

int dfs(int* head, Edge* edges, int curr, Color color, Color* colors) {
  *(colors + curr) = color;
  int i, nei;
  for (i = *(head + curr); i; i = (*(edges + i)).next) {
    nei = (*(edges + i)).to;
    if (*(colors + nei) == color) return 0; // 我邻居的颜色与我相同，表明存在着冲突
    if (*(colors + nei) == UNKNOWN && 
        !dfs(head, edges, nei, color == BLACK ? WHITE : BLACK, colors))
      return 0;
  }
  return 1;
}

int main(const int argc, const char* argv[]) {
  int n, m, u, v;
  fscanf(stdin, "%d %d", &n, &m);
  
  int head[n + 1]; 
  Edge edges[m << 1 | 1];
  memset(head, 0x0000, sizeof head);
  
  int i = 0;
  while (m--) {
    fscanf(stdin, "%d %d", &u, &v);
    addEdge(head, edges, u, v, ++i);
    addEdge(head, edges, v, u, ++i);
  }
  
  Color colors[n + 1];
  memset(colors, UNKNOWN, sizeof colors);
  
  // 图中可能有多个连通分量 (连通分量 == 极大的连通子图)
  for (u = 1; u <= n; ++u)
    if (*(colors + u) == UNKNOWN && !dfs(head, edges, u, BLACK, colors))
      return fputs("No", stdout), 0;
  
  return fputs("Yes", stdout), 0;
}