图，有有向图，无向图，稠密图，简单图······
算法，有贪心法，二分法，模拟法，倍增法······
那，二分图是啥？
二分法+有向图？
于是，我查了许多资料，才对它有一定了解。
二分图：二分图，是图论中的一种特殊模型，设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且同一集合中不同的两点没有边相连。
这就是二分图。
举个栗子吧：
这是不是二分图？
反正我第一次看觉得不是
其实，是的，他是二分图，尽管看上去是连着的。
若我们将图中的一些边转一下，变成：
这就是一个明显的二分图。
集合A与B中的点互不相连。
因此，在手动判定二分图时学会转边！
辣魔，二分图要用计算机判定怎么实现？
数竞大佬：简单！
！！！染色大法！！！
有没有熟悉的感觉
0表示还未访问，1表示在集合A中，2表示在集合B中。
col（color）储存颜色。
初始化为0.
上代码：
其实是模板
可以记忆。
1 vector <int> v[N]; 2 void dfs(int x,int y){ 3 col[x]=y; 4 for (int i=0; i<v[x].size(); i++) { 5 if (!col[v[x][i]]) dfs(v[x][i],3-y); 6 if (col[v[x][i]]==col[x]) FLAG=true; //产生了冲突 7 } 8 } 9 for (i=1; i<=n; i++) col[i]=0; //初始化 10 for (i=1; i<=n; i++) if (!col[i]) dfs(i,1); //dfs染色 11 if (FLAG) cout<<"NO"; else cout<<"YES";
下一章我们将讲到二分图的匹配，我们明天见。