交叉染色法

题意： # 给出n个点m条边，以及已知的好点和坏点。一个边连接的2个点一定是一好一坏，问是否有合法方案，使得每个点被确定好坏。

题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333.

题目链接：hdu 5285 题目lianjie 题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。

hdu 5215 思路：询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以有相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。

hdu 4751 题目链接 题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。 思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。

uva10004题目链接 题意：给出一个无向图，问是否可以组成二分图。 思路：交叉染色法。 首先任意取出一个顶点进行染色，和该节点相邻的点有三种情况： **　1.未染色 那么继续染色此节点(染色为另一种颜色)**