图的二着色问题

问题描述：对于给定的图G，如果存在一种用两种颜色对顶点着色的方案，使得图中任意一条边所连接的两个顶点着不同颜色，则称图G是可二着色的。

实验任务：对于给定的图G，计算G是否可二着色

数据输入：第1行有2个正整数m, n，表示给定图G有n个顶点和m条边，顶点编号1,2,...,n。接下来m行中，每行有两个正整数u,v，表示图G的一条边(u,v)

结果输出：可二着色输出"Yes"，否则输出"No"

直观想法，深搜或者广搜，一个顶点涂一个颜色，下一个顶点涂相反颜色。如果搜索到涂过的顶点，判断与当前顶点颜色是否相同，是则表明无法二着色，立即退出。直至全部搜索完成。

事实上，图如果无法二着色，那么必然有环，且环的顶点数必然为奇数，但是这个有什么算法呢，emmm，没想到，直接用最简单直观的深搜吧

#include <bits/stdc++.h>
using namespace std;

typedef struct{
 int vexnum; //顶点数 
 int arcnum; //边数 
 int **arc; //邻接矩阵
}Matrix_Graph;

Matrix_Graph CreateNewGraph(int n, int m)
{
 int i, j;
 Matrix_Graph graph;
 
 graph.vexnum = n;
 graph.arcnum = m;
 graph.arc = new int*[n+1];
 for(i = 1; i <= n; ++i){
  graph.arc[i] = new int[n+1];
  for(j = 1; j <= n; ++j)
   graph.arc[i][j] = 0;   
 }
 while( m-- ){
  cin >> i >> j;
  graph.arc[i][j] = graph.arc[j][i] = 1;
 }
 return graph;
}

void dfs(const Matrix_Graph& graph, int vex, bool visited[], bool color[], bool nowColor, bool& res)
{
 visited[vex] = true; // 标记访问 
 color[vex] = nowColor; // 涂色 
 cout << "vex " << vex << ": ";
 if( color[vex] ){
  cout << "red\n";
 }else{
  cout << "black\n";
 } 
 
 for(int i = 1; i <= graph.vexnum; ++i)
 {
  // 首先判断两点是否连通 
  if( graph.arc[vex][i] == 1 )
  {
   // 若访问过，且颜色一致，说明失败 
   if( visited[i] && color[i]==nowColor ){
    res = false;
    return; 
   }else if( !visited[i] ){
    // !nowColor表示下一个顶点涂另一种颜色 
    dfs(graph, i, visited, color, !nowColor, res);
    if( !res )
     return; 
   }   
  }
 }  
}

void Dfs_Graph(const Matrix_Graph& graph, bool& res)
{
 bool visited[graph.vexnum+1] = {false};
 bool color[graph.vexnum+1] = {false};
 bool nowColor = false;
 for(int i = 1; res && i<=graph.vexnum; ++i)
  if( !visited[i] )
   dfs(graph, i, visited, color, nowColor, res); 
}

bool Cover_2color(const Matrix_Graph& graph)
{
 bool res = true;
 Dfs_Graph(graph, res);
 return res;  
}

int main()
{
 int n, m;
 cin >> n >> m;
 
 Matrix_Graph graph = CreateNewGraph(n, m);
 
 if( Cover_2color(graph) ){
  cout << "Yes\n";
 }else{
  cout << "No\n";
 }
 
 return 0;
}
//Test1 
//12 10
//1 3
//1 6
//2 8
//3 7
//4 5
//5 6
//5 8
//2 9
//9 10
//11 12

//Test2
//12 10
//1 3
//1 6
//2 8
//3 7
//4 5
//5 6
//5 8
//2 9
//9 10
//8 9