update:还请各位不要点赞，补充本就应该在原本的题解之后。

谨以此题解作为对 Tweetuzki 神仙的题解的补充。

题解的说明顺序按照每部分在我代码中的先后顺序。

找出合法集合的具体步骤

现在递归到了 $x$ 点，当前在找包含 $bel$ 的合法集合。已经确定要加入的元素、与当前集合某点相邻但还未确定是否加入的元素、与当前集合某点相邻且确定不加入的元素，分别存在 $\texttt{std::set<int>in,neighbor,out}$ 中。

• 首先将 $x$ 加入 $\texttt{in}$ 中并从 $\texttt{neighbor}$ 中删除 $x$（若没有则忽略）。
• 检查 $\texttt{in,neighbor,out}$ 的大小是否满足题意。
• 若当前的 $\texttt{in}$ 符合条件，则此次搜索成功。将所有在 $\texttt{in}$ 中的点标记，以后不再搜索。记录下这个集合 $\texttt{in}$，直接返回 $\text{true}$。
• 扫描所有与 $\texttt{in}$ 中某点相邻的点 $v$，若 $v$ 不在 $\texttt{in,neighbor,out}$ 的任意一个中，将其加入 $\texttt{neighbor}$。
• 对于集合 $\texttt{neighbor}$ 中的每个元素 $v$，递归尝试能否将其加入当前集合 $\texttt{in}$ 中，若可行，直接返回 $\text{true}$，否则将其从 $\texttt{neighbor}$ 中移至 $\texttt{out}$ 中。
• 若此次搜索完成仍未找到可行解，返回 $\text{false}$。

各种无解判断

• （Tweetuzki 神仙提及的）有两个人不是双向的朋友关系。可以使用 $\texttt{map}$ 套 $\texttt{pair}$ 来判断。
• 某个点连出的边不小于 $p+q$。
• 某个点找不到对应的合法集合。

对于第二个步骤的证明的补充

（先照抄一小段）题设：设有两个合法点集 $A,B$，则 $A \setminus B$ 和 $B \setminus A$ 至少有一个合法。（这里的 $\setminus$ 是减去的意思）

证明：令 $C$ 为 $A \cap B$。考虑减去 $C$ 过后会对两个点集产生什么影响。

首先考虑增加了哪些连向集合外的边。以 $A$ 为例，它增加了本身与 $C$ 的连边数，设为 $a$，$B$ 的同理设为 $b$。

然后考虑失去了哪些边。因为失去了整个 $C$，所以 $C$ 连向外部的边全部失去。这部分既包含连向 $A,B$ 的边，也包含连向其他点的边，后者设为 $c$。

$A$ 和 $B$ 边的变化量就分别是 $a-b-c$ 和 $b-a-c$。因为 $a-b$ 和 $b-a$ 互为相反数，所以其中至少有一个非正，减去 $c$ 也非正，所以边数满足条件，而点数又变小，所以合法。

附一个自己的代码，为了编写方便可能与描述有些出入。

#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<set>
const int maxn=2.5e3+5;
const int maxm=3e4*2+5;
const int maxp=15;
struct edge{
	int to;
	int next;
}qxx[maxm];
int qxx_cnt,h[maxn];
void add(int x,int y){
	qxx[++qxx_cnt]=(edge){y,h[x]};
	h[x]=qxx_cnt;
	return;
}
int n,p,q;
std::set<int>group[maxn];
bool inside[maxn];
void no_sol(){
	printf("detention");
	exit(0);
	return;
}
bool can(std::set<int>gave){
	if((int)gave.size()>p)return false;
	int cou=0;
	for(int x:gave){
		for(int i=h[x];i;i=qxx[i].next){
			int v=qxx[i].to;
			if(!gave.count(v))cou++;
		}
	}
	return cou<=q;
}
std::set<int>in,near,out;
bool search(int x,int bel,std::set<int>in,std::set<int>near,std::set<int>out){
	in.insert(x);
	if(x!=bel)near.erase(x);
	if((int)in.size()>p||(int)out.size()>q||(int)(in.size()+near.size()+out.size())>p+q)return false;
	if(can(in)){
		group[bel]=in;
		for(int x:in)inside[x]=true;
		return true;
	}
	for(int i=h[x];i;i=qxx[i].next){
		int v=qxx[i].to;
		if(!in.count(v)&&!near.count(v)&&!out.count(v))near.insert(v);
	}
	while(!near.empty()){
		int v=*(near.begin());
		if(search(v,bel,in,near,out))return true;
		near.erase(near.begin());
		out.insert(v);
	}
	return false;
}
signed main(){
	std::set<std::pair<int,int>>apr;
	apr.clear();
	scanf("%d%d%d",&n,&p,&q);
	for(int i=0;i<n;i++){
		int tot;
		scanf("%d",&tot);
		if(tot>=p+q)no_sol();
		for(int j=1;j<=tot;j++){
			int x;
			scanf("%d",&x);
			add(i+1,x+1);
			if(i<x)apr.insert({i,x});
			else{
				if(!apr.count({x,i}))no_sol();
				else apr.erase({x,i});
			}
		}
	}
	if(!apr.empty())no_sol();
	for(int i=1;i<=n;i++){
		if(inside[i])continue;
		in.clear();
		near.clear();
		out.clear();
		if(!search(i,i,std::set<int>(),std::set<int>(),std::set<int>()))no_sol();
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			std::set<int>ls=group[i],rs=group[j];
			for(int x:group[i])if(rs.count(x))rs.erase(x);
			for(int x:group[j])if(ls.count(x))ls.erase(x);
			if(can(ls))group[i]=ls;
			else group[j]=rs;
		}
	}
	int cou=0;
	for(int i=1;i<=n;i++)if(!group[i].empty())cou++;
	printf("home\n");
	printf("%d\n",cou);
	for(int i=1;i<=n;i++){
		if(group[i].empty())continue;
		printf("%d",(int)(group[i].size()));
		for(int x:group[i])printf(" %d",x-1);
		printf("\n");
	}
	return 0;
}

感谢您的阅读。