分组问题

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 fenzu.in 输出文件 fenzu.out

【问题描述】

你的任务是把一些人分成两组,使得:

·每个人都被分到其中一组;

·每个组都至少有一个人;

·一组中的每个人都认识其他同组成员;

·两组的成员人数近两接近。

这个问题可能有多个解决方案,你只要输出任意一个即可,或者输出这样的分组法不存在。

【输入】

为了简单起见,所有的人都用一个整数标记,每个人号码不同,从1N

输入文件的第一行包括一个整数N2N100),N就是需要分组的总人数;接下来的N行对应了这N个人,按每个人号码的升序排列,每一行给出了一串号码Aij1AijNAiji),代表了第i个人所认识的人的号码,号码之间用空格隔开,并以一个“0”结束。

【输出】

如果分组方法不存在,就输出信息“No solution”(输出时无需加引号)至输出文件;否则用两行输出分组方案;第一行先输出第一组的人数,然后给出第一组成员的号码,每个号码前有一个空格,同理给出第二组的信息。每组的成员号码顺序和组别顺序并不重要。

【样例】

teams.in                     teams.out

5                            3 1 3 5

2 3 5 0                      2 2 4

1 4 5 3 0

1 2 5 0

1 2 3 0

4 3 2 1 0