【分组问题】

题目描述

简单的说有 N 个人参加一个活动,已知每个人认识哪些人(注意这种认识是单向的),求问是否能将所有人分成两个组使得每个组组内所有人都互相认识?注意:自己认识自己,即一个人也算(YES)。

输入格式

这里有多组数据(不超过 5 组)。
每组数据第一行输入一个数 N ,表示有 N 个人参加活动(2<=N<=100),人从 1 开始编号到 N 结束。
接下来 N 行中每行有多个数字,中间用空格隔开并以 0 作为这一行结束。第 i 行的数字表示第 i 个人认识哪些人。如第一行 3 0 表示 1 号认识 3 号。

输出格式

对于每组数据输出一行,如果可行输出“YES”否则输出“NO”(不含引号)。

样例数据 1

输入

3
3 0
1 0
1 2 0

输出

YES

备注

【数据范围】
30% 数据满足,N<=10
60% 数据满足,N<=20
100% 数据满足,N<=100

不得不说,这道题的数据太水了,乱搞都能AC……后来才知道正解是通过人与人的认识关系建立反图(不认识的关系),然后进行交叉染色,如果目标节点染的是和自己一样的颜色即可判断有奇数环,就说明至少有一个人不能被分在两组中,就NO了,否则全遍历一遍都OK就YES。

下面是正解:

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*