自动搬运

查看原文

来自洛谷，原作者为

	耳朵龙_ 老师说不要看没用的东西，看来不能照镜子了

搬运于2025-08-24 21:48:55，当前版本为作者最后更新于2023-09-20 21:27:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本题现有题解没有提供答案为 $n$ 的证明，补一个证明。

将人看做点，认识关系看作无向边，原题意等价于：给定一张无向图，$0/1$ 染色后，称一个点是好的，当且仅当与之相邻且同色的点的个数为偶数。构造一种染色方案使好点的个数最多。

记点 $i$ 的颜色为 $col_i$，度数为 $deg_i$，图的边集为 $E$。

假设好点个数可以为 $n$，那么当好点数为 $n$ 时，根据与点 $i$ 相邻且同色的点的个数为偶数，可知点的颜色满足一个 $n$ 行的异或方程组，第 $i$ 行为：

$$\begin{cases}\bigoplus\limits_{(i,v)\in E}col_v=0&2\mid deg_i\\\left(\bigoplus\limits_{(i,v)\in E} col_v\right)\oplus col_i=1&2\nmid deg_i\end{cases} $$

若该方程组有解，那么容易构造出使好点个数为 $n$ 的染色方案，下面证明该方程组一定有解。

若该方程组无解，则必然能将某几行异或起来，使得等号左边各未知数系数均为 $0$，而等号右边常数为 $1$。即存在 $S\subseteq\mathbb{N^*}$，$\bigoplus\limits_{i\in S}$ 第 $i$ 个方程左边 $=0$，$\bigoplus\limits_{i\in S}$ 第 $i$ 个方程右边 $=1$。

称点 $i$ 被选择，当且仅当 $i\in S$。称 $v$ 属于 $u$ 的邻域，当且仅当 $(u,v)\in E$。则方程组无解当且仅当存在 $S$ 使得：

• 选择了奇数个奇度点（右边异或和为 $1$）
• 每个被选择的奇度点的邻域内都选了奇数个点，其他点的邻域内都选了偶数个点（左边各未知数系数均为 $0$）

可以根据 $S$ 构造一张无向图 $G'$，其点集与原图相同，边集为 $\{(u,v)\mid u\in S\lor v\in S\}\cap E$。由于 $G'$ 是一张无向图，其度数和为偶数。在 $G'$ 中，容易发现被选择的奇度点度数为奇数，而其他点度数为偶数，由于被选择的奇度点有奇数个，$G'$ 的度数和为奇数。前后矛盾，因此这样的选点方案不存在，方程组有解。

高斯消元解该方程组，输出方案即可，时间复杂度 $O\left(\frac{n^3}{\omega}\right)$。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n,m,b[N];
bitset<N>a[N];
int main(){
	scanf("%d",&n);
	for(int i=1,l,x;i<=n;++i){
		scanf("%d",&l),a[i][n+1]=a[i][i]=l&1;
		while(l--) scanf("%d",&x),a[i][x]=1;
	}
	for(int i=1,l;i<=n;++i){
		for(l=i;l<=n&&!a[l][i];++l) ;
		if(l<=n){
			if(l^i) swap(a[i],a[l]);
			for(l=1;l<=n;++l) if(l!=i&&a[l][i]) a[l]^=a[i];
		}
	}
	for(int i=n;i;--i) if(a[i][i]&a[i][n+1]) b[++m]=i;
	printf("%d\n",m);
	while(m) printf("%d ",b[m--]);
	return 0;
}