1 什么是二分图

  一个图用两种颜色涂（橙黄和橘绿），相邻节点不能同色，如下图，4与5相邻且同色，所以不是二分图。

2 进入情境

  第一版：设每个节点都是一个炮仗，横线即引线，相连的炮仗能被他的邻居点燃，即一个炮仗响了，和他相连的炮仗也将会被点燃。

1. 初始化：选一个炮仗，涂成绿色，放到包里。
2. 从容而得意的，从包里取一个炮仗：点燃
3. 被引线相连的也将会被引燃，先把他们标记为不同的颜色（如黄色），并放到包里。
   • 注意： 如果下一个炮仗已有颜色且和刚刚的颜色一样，说明相邻的颜色重复，不是二分图，退出。
4. 若包里还有节点，就回到步骤2继续点。
5. 全程安全放炮，说明是二分图。

3 代码实现

#include <iostream>
#include <vector>
#include <string>
#include <queue>using namespace std;
#define see(x) cout << x << endl
#define see2(x, y) cout << (x) << (y) << endl
class Solution
{
public:using _num = size_t;bool bfs(vector<vector<int>> &graph, vector<int> &vis,_num id){enum{no_color,yellow,green};bool ans = true;// 最开始取一个涂色，放入包里。bague<int> bag;vis.at(id) = yellow;bag.push(id);while (!bag.empty() && ans){int now_id = bag.front();//取一个出来bag.pop();//点燃，嘭！int now_color = vis.at(now_id);//记录当前颜色//将被引燃的邻居小炮们for (auto &nxt : graph.at(now_id)){if (vis.at(nxt) == no_color){   //无颜色就涂成不同色vis.at(nxt) = now_color !=yellow?yellow:green;bag.push(nxt);//放入包里}else//已经有颜色{if (vis.at(nxt) == now_color){//颜色重复了ans = false;break; //不是二色图}else{;//不重复，什么也不做}}}}return ans;}bool isBipartite(vector<vector<int>> &graph){_num n = graph.size();vector<int> vis(n, 0); // 0 not visit, 1 one color, 2 another colorbool ans=true;for(_num id=0;id<n;++id){if(0==vis.at(id))//可能有多个子图ans=ans && bfs(graph, vis,id);}return ans;}
};void test()
{//领接链表vector<vector<int>> G{{1,3},{0,2},{1,3},{0,2,4,5},{3,5},{3,4}};Solution sol;if (sol.isBipartite(G)){see("Accept!!!");}else{see("something error.");}
}int main()
{test();return 0;
}

4 BFS是什么？

   一圈放完，再放外面一圈，炮声渐远……
   BFS 广度优先搜索，从起点开始，将所有和它相邻的结点都搜索一遍，重复该操作，层层铺开，地毯式搜索，好似水中的涟漪，从中心开始，向四周扩散，直到遍历完整个图。