C 解法, 执行用时: 1ms, 内存消耗: 372KB, 提交时间: 2020-05-20

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10001
typedef int Vertex;
typedef int WeightType;
typedef struct GNode *PtrToGNode;
struct GNode{
    int N;
    int Ne;
    WeightType G[MAXSIZE][MAXSIZE];
};
typedef PtrToGNode MGraph;
      
int color=0;
int flag=1;
      
MGraph ReadG();
void dfs(MGraph Graph,int cur,int color);
int swap(int color);
int known[MAXSIZE]={0};
int Color[MAXSIZE]={-1};
      
      
int main(){
    MGraph Graph;
    int i;
    Graph=ReadG();
    Color[0]=1;
    known[0]=1;
    dfs(Graph,1,0);
    if(flag==1) printf("Yes\n");
    else printf("No\n");
    //for(i=0;i<Graph->N;i++){
    //  printf("known[%d]=%d\n Color[%d]=%d\n",i,known[i],i,Color[i]);
    //}
}
      
      
MGraph ReadG(){
    MGraph P;
    int i,j,k;
    int m,n;
          
    P=(MGraph)malloc(sizeof(struct GNode));
      
    scanf("%d%d",&P->N,&P->Ne);
      
    for(i=1; i<=P->N; i++) {
        for(j=1; j<=P->N; j++) {
            P->G[i][j]=-1;
        }
    }
     
      
    for(i=0;i<P->Ne;i++){
        scanf("%d%d",&m,&n);
        P->G[m][n]=1;
    }
     
         
          
    return P;
}
      
void dfs(MGraph Graph,int cur,int color){
    int i;
    if(flag==0) return;
    if(known[cur]==1){
        if(Color[cur]!=color){
            //printf("color%d:error\n");
            flag=0;
        }
        return;
    }
    else{
        Color[cur]=color;
        known[cur]=1;
        //printf("color%d:%d\n",cur,color);
    }
    for(i=1;i<=Graph->N;i++){
        if(Graph->G[cur][i]==1){
        //  printf("%d to %d\n",cur,i);
            dfs(Graph,i,swap(color));
            if(flag==0) return;
        }
    }
          
    return;
}
      
int swap(int color){
    if(color==0) color=1;
    else color=0;
    return color;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2021-07-17

#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;
}