hdu 4751 Divide Groups (反向建图,判断二分图,交叉染色法)

hdu 4751 题目链接

题意:n个人,给出每个人认识的人的信息。问能否将这些人分成两组,保证每组至少1个人,并且两两互相认识。

思路:首先是反向建图。由于要求同组内两个人互相认识,那么两个人u,v,只要u不认识v或者v不认识有一个满足,就连接双向边u,v,表示u,v不能分到同一组。

由于图反向以后不保证联通,因此求补图以后可能会得到几个联通分量。

而合法的条件是,每个联通分量都合法。

不合法的条件是,只要由一个联通分量不合法。

以及:之前把交叉染色部分写错了。上道题可以通过纯粹是因为数据水。。?

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz