PS：这是今天上午NOIP模拟赛的T3。
题意
N个小朋友，每个小朋友最多有3个敌对小朋友，
问是否能把他们分成两组，使得这N个小朋友最多只有一个敌对小朋友在一组。
思路
考场上想肯定与二分图有关，最后没想出来，打了15分暴力就走了（最后还只有10分） 。
考后听完xqw大佬讲题过后，发现思路很巧妙。
首先将两组看作两个集合，初始时都在\(1\)集合。每一次将两个集合中不符合题目要求的点（即在当前集合中敌对数\(>=2\)的点）换到另外一个集合中去，重复执行此操作，最终一定会得到答案。
对没错，这道题一定有解，不可能输出NO SULOTION，这也就是此题奇妙之处了。
证明
首先每次将点换集合的条件是：在当前集合中敌对数\(>=2\)。而题目说过每个点最多一共有\(3\)个敌对点，所以：
换集合后，原来集合敌对数至少\(-2\)，新集合敌对数至多\(+1\)。
所以每次操作至少会减少一个敌对数，所以一直操作一定可以满足题意。
总结
这道题主要考的还是思维，证明的思路非常难想但又非常优美。
Code
#include<bits/stdc++.h>
using namespace std;
#define ls id << 1
#define rs id << 1 | 1
const int MAXN = 1e5 + 10;
int n,c[MAXN],x,cnt,head[MAXN],col[MAXN],q[MAXN],ans1[MAXN],ans2[MAXN],top1,top2;
bool vis[MAXN];
struct Node
{
int u,v,nxt;
}e[MAXN << 4];
void Add(int u,int v){e[++cnt] = {u,v,head[u]};head[u] = cnt;}
signed main()
{
memset(head,-1,sizeof head);
scanf("%d",&n);
for(int i = 1;i <= n;i++)
{
scanf("%d",&c[i]);
for(int j = 1;j <= c[i];j++)
{
scanf("%d",&x);
Add(i,x);
}
}
int l = 0,r = 0;
for(int i = 1;i <= n;i++) col[i] = vis[i] = 1,q[r++] = i;
for(;l != r;l++)
{
int u = q[l],sum = 0;
vis[u] = false;
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(col[u] == col[now]) sum++;
}
if(sum >= 2)
{
col[u] = 3 - col[u];
for(int i = head[u]; ~ i;i = e[i].nxt)
{
int now = e[i].v;
if(vis[now] == false) if(r < 1e6) q[r++] = now;
}
}
}
for(int i = 1;i <= n;i++)
{
if(col[i] == 1) ans1[++top1] = i;
if(col[i] == 2) ans2[++top2] = i;
}
if(top1 < top2 || (top1 == top2 && col[1] == 1))
{
printf("%d\n",top1);
for(int i = 1;i <= top1;i++) printf("%d ",ans1[i]);
}
else
{
printf("%d\n",top2);
for(int i = 1;i <= top2;i++) printf("%d ",ans2[i]);
}
return 0;
}