题意： 给出n个点m条边，以及已知的好点和坏点。一个边连接的2个点一定是一好一坏，问是否有合法方案，使得每个点被确定好坏。 思路： 判断二分图。 先染已知的，再染未知的。 注意判掉没有出现的点。 注意有多个联通块。 1 2 /* *********************************************** 3Author :111qqz 4Created Time :2017年10月26日 星期四 12时53分06秒 5File Name :A.cpp 6************************************************ */ 7 8 #include …

题目链接 题意：找两个不相交点集使得对于每一条边至少有一个顶点在点集中 思路：判断能否构成二分图。染色即可。 需要注意的是。。。答案有特判。。和样例不一样我还以为是自己做错了2333. /* *********************************************** Author :111qqz Created Time :2016年09月03日 星期六 01时04分40秒 File Name :code/hdu/687A.cpp ************************************************ */ #include <cstdio> #include …

题目链接：hdu 5285 题目lianjie 题意：给定n个小朋友，以及小朋友之间的关系，要求将小朋友分成两组，**并且每组至少一个人，**现在问能否这样分组，如果有解，输出两组的人数，并保证第一组的人数尽可能地大。 思路：。。。一开始看到n的数据范围。。。想当然的以为会给认识的人的关系。。。尼玛。。。求个补图就够受的了。。。。不会做，卒。 结果发现。。竟然给的是两个人不认识的关系。。。2333 那么我们来交叉染色。。。 实际上交叉染色的过程中，颜色相同的点属于二分图中相同的点集合。 交叉染色其实是在模拟交错轨的过程...？ 由于图不一定联通，可能由多个联通块。 我们在交叉染色的时候记录一下0,1的个数（也就是两个点集的大小） 然 …

hdu 5215 思路:询问一个无向图，是否存在奇数环，以及是否存在偶数环。（不同的环之间可以由相同的点，不能有相同的边） 思路：一开始的想法是，根据染色的奇偶性，如果染色到某个之前染色过的点，和当前要染的颜色相同，说明存在奇数环，不同，说明存在偶数环。 感觉很有道理的做法。。。然而错了。。。发现是忽略了上面说的，不同的环之间由相同的点的情况。 比如这组数据： 5 6 1 2 2 3 3 1 1 4 4 5 5 1 两个三元环扣在一起。 实际上是既有奇数环，又有偶数环的。 但是按照我的做法，由于每次只去染没有染过的点，无法发现偶数环。 因此正解是增加一步回溯，这样使得之前存在与某个环中的点还可以出现在其他环中。 然而这样复杂度会 …

hdu 4751 题目链接 题意：n个人，给出每个人认识的人的信息。问能否将这些人分成两组，保证每组至少1个人，并且两两互相认识。 思路：首先是反向建图。由于要求同组内两个人互相认识，那么两个人u,v，只要u不认识v或者v不认识有一个满足，就连接双向边u,v，表示u,v不能分到同一组。 由于图反向以后不保证联通，因此求补图以后可能会得到几个联通分量。 而合法的条件是，每个联通分量都合法。 不合法的条件是，只要由一个联通分量不合法。 以及：之前把交叉染色部分写错了。上道题可以通过纯粹是因为数据水。。？ /* *********************************************** Author :111qqz …

uva10004题目链接 题意：给出一个无向图，问是否可以组成二分图。 思路：交叉染色法。 **首先任意取出一个顶点进行染色,和该节点相邻的点有三种情况:** **　1.未染色 那么继续染色此节点(染色为另一种颜色)** **　2.已染色但和当前节点颜色不同 跳过该点** **　3.已染色并且和当前节点颜色相同 返回失败(该图不是二分图)** 学习链接 upd:更正dfs中的一个错误。 把dfs(v,1-x)改成了 if (!dfs(v,1-x)) return false; 之前的写法中，当前层之后的层的没有起到任何作用。。。 而实际上应该是后面只要某一层不满足，整体就该为false. 写成这样这题还能过我也是醉了。。。。 /* …