二分图判定二分图：指的是可以用两个不相交的集合表示该图的节点，然后该图的每一条边的端点分别位于这两个集合中。判断二分图方法：用染色法，把图中的点染成黑色和白色。首先取

Question

二分图判定
二分图：
指的是可以用两个不相交的集合表示该图的节点，然后该图的每一条边的端点分别位于这两个集合中。
判断二分图方法：
用染色法，把图中的点染成黑色和白色。
首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现有相邻且同色的点，那么就退出，可知这个图并非二分图（一次bfs，O（n））。
例题：
在某学校，学生在离校之前必须做两个考试。这意味着学校必须提供一些可选的考试。每个学生必须选择两个不同的科目。根据规则每个学生不允许在同一天完成两个考试。所以学校必须安排好这些考试。
一个学校不想让老师太辛苦，他们想在两天之内安排所有这些考试。在第一天安排一些考试，在第二天安排其它的考试。要求你写一个这样的程序来看看是否可以做到让每个学生都能参加他们的考试。
输入：
在第一行有两个整数N和M,(1<=N<=200,1<=m<=30000)N代表可选择的考试的科目数量，M代表学生的人数。下面的M行中分别表示每一个学生选择的代表两个考试科目的数字。
输出：
如果安排方法存在，在第一行写"yes",在第二行输出在第一天必须安排的考试项目的数量，在第三行输出第一天代表考试科目的数字。如果存在多个安排方法，输出其中一个就可以了。
如果安排方法不存在，输出"no"
测试样例
输入
4 4
1 2
3 4
2 4
1 3
输出
是的
2
1 4
判断一个图是否是二分图 黑白染色
题意解释：给出一个图的边，对这个图进行黑白染色，不能染色则输出no
能染色输出黑色或者白色的个数，并且输出点的序号
每个人选的两个课程之间连无向边,然后DFS时进行黑白染色,DFS树上每个结点和他的父亲节点不同色.然后考虑横向边和返祖边,如果有一条边两边的结点颜色相同则说明无解,否则将白色的考试放在一天,黑色的放在另一天就可以了…

c++语言，求程序

Answer 1

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int edge[201][201];
bool vis[201];
bool has[201];
int color[201]; // 0 for white, 1 for black

int main() {
 int N, M;
 cin >> N >> M;
 memset(edge, 0, sizeof(edge));
 memset(vis, 0, sizeof(vis));
 memset(has, 0, sizeof(has));
 for (int i = 0; i < M; i++) {
  int a, b;
  cin >> a >> b;
  has[a] = has[b] = 1;
  edge[a][b] = edge[b][a] = 1;
 }
 bool flag = true;
 int counts = 0;
 for (int i = 1; flag && i <= N; i++) {
  if (vis[i] || !has[i]) continue;
  queue<int> q;
  q.push(i);
  vis[i] = true;
  color[i] = 0;
  counts++;
  while (flag && !q.empty()) {
   int temp = q.front();
   q.pop();
   for (int j = 1; j <= N; j++) {
    if (!edge[temp][j]) continue;
    if (vis[j]) {
     if (color[j] == color[temp]) {
      flag = false;
      break;
     }
     else {
      continue;
     }
    }
    vis[j] = true;
    color[j] = 1 - color[temp];
    counts += 1 - color[j];
    q.push(j);
   }
  }
 }
 if (flag) {
  cout << "yes" << endl;
  cout << counts << endl;
  bool first = true;
  for (int i = 1; i <= N; i++) {
   if (vis[i] == 1 && color[i] == 0) {
    if (first) {
     first = false;
    }
    else {
     cout << " ";
    }
    cout << i;
   }
  }
  cout << endl;
 }
 else {
  cout << "no" << endl;
 }
// system("pause");
}