POI #Year2011 #数学

考虑按照 \(deg\) 排序，然后暴力加入，这样可以得到一个极大的子集

方案数分两种，一种为从团内去掉一个 \(deg=siz-1\) 的点，或者是将一个团外的 \(deg=siz-1\) 的点与一个团内的交换

// Author: xiaruize
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 5e3 + 10;

int n;
int rnk[N], deg[N];
bitset<N> bt[N], cur;

bool cmp(int x, int y)
{
	return deg[x] > deg[y];
}

void solve()
{
	cin >> n;
	rep(i, 1, n)
	{
		rnk[i] = i;
		cin >> deg[i];
		rep(j, 1, deg[i])
		{
			int x;
			cin >> x;
			bt[i][x] = true;
		}
	}
	sort(rnk + 1, rnk + n + 1, cmp);
	int cnt = n;
	rep(i, 1, n)
	{
		if ((bt[rnk[i]] & cur).count() == cur.count())
			cur[rnk[i]] = true;
		else
		{
			cnt = i - 1;
			break;
		}
	}
	rep(i, cnt + 1, n)
	{
		rep(j, i + 1, n)
		{
			if (bt[rnk[i]][rnk[j]])
			{
				cout << "0\n";
				return;
			}
		}
	}
	int res = 1;
	if (cnt == n)
		res--;
	if (cnt != 1)
	{
		rep(i, 1, cnt) if (deg[rnk[i]] == cnt - 1)
			res++;
	}
	rep(i, cnt + 1, n)
	{
		if (deg[rnk[i]] == cnt - 1)
		{
			rep(j, 1, cnt)
			{
				if (!bt[rnk[i]][rnk[j]])
				{
					if (deg[rnk[j]] == cnt - 1)
						res++;
					break;
				}
			}
		}
	}
	cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}