4328: JSOI2012 始祖鸟
Time Limit: 10 Sec Memory Limit: 256 MBSec Special Judge
Submit: 76 Solved: 52
[Submit][Status][Discuss]
Description
最近，进香河地带出现了一家“始祖鸟专卖店”，然而这并不只是一时的心血来潮。
早在远古时期，进香河地带就以其秀美的环境和适宜的温度吸引了成群的始祖鸟。始祖鸟是一种团结的鸟类，它们总是通过各种方式来增强种群内部的交流，聚会则是其中之一。因为聚会不但可以增强朋友之间的友谊，而且可以认识新的朋友。
现在有N只始祖鸟，我们从1开始编号。对于第i只始祖鸟，有Mi个认识的朋友，它们的编号分别是Fi,1，Fi,2，…，Fi,Mi。朋友的认识关系是单向的，也就是说如果第s只始祖鸟认识第t只始祖鸟，那么第t只始祖鸟不一定认识第s只始祖鸟。
聚会的地点分为两处，一处在上游，一处在下游。对于每一处聚会场所，都必须满足对于在这个聚会场所中的始祖鸟，有恰好有偶数个自己认识的朋友与之在同一个聚会场所中。当然，每一只始祖鸟都必须在两处聚会场所之一。
现在需要你给出一种安排方式。你只需要给出在上游的始祖鸟编号，如果有多组解，请输出任何一组解。
Input
输入数据包含N+1行，第一行是数字N，代表始祖鸟的个数。
之后的N行，第i+1行的第一个数字是M[i]，表示第i只鸟的朋友个数。之后有M[i]个数字依次为
F[i][1]，F[i][2]，…，F[i][M[i]]表示第i只始祖鸟朋友的标号。
Output
输出数据包含2行，第一行有一个非负整数k，表示在上游参加聚会的始祖鸟个数。第二行有k个正整数，表示在这个k只始祖鸟的编号，你可以以任意顺序输出这些编号。如果无法满足要求，只输出一行“Impossible”。
高斯消元+bitset
把每只鸟在上游或下游看成一个0/1变量。
对于偶数条出边的鸟，要求它指向的鸟选1的为偶数个。
对于奇数条出边的鸟，如果它选1，要求它指向的鸟选1的为偶数个，否则为奇数个。
#include<bits/stdc++.h>
#define N 2005
using namespace std;
int f[N];
int n;
bitset<N>a[N];
int main()
{
scanf("%d",&n);
int tmp,js;
for(int i=1;i<=n;i++)
{
scanf("%d",&js);
if(js&1)a[i][i]=a[i][0]=1;
while(js--)scanf("%d",&tmp),a[i][tmp]=1;
}
for(int i=1;i<n;i++)
{
int p=0;
for(int j=i;j<=n;j++)if(a[j][i]){p=j;break;}
if(!p)continue;
if(p!=i)swap(a[p],a[i]);
for(int j=1;j<=n;j++)if(a[j][i]&&j!=i)a[j]^=a[i];
}int t=0;
for(int i=n;i;i--)
{
if(a[i][i])
{
f[i]=a[i][0];
if(f[i])t++;
}
else if(a[i][0])
{
puts("Impossible");
return 0;
}
}
printf("%d\n",t);
for(int i=1;i<=n;i++)if(f[i])printf("%d ",i);
return 0;
}