Logo Universal Online Judge

UOJ

时间限制:2 s 空间限制:1024 MB

#2742. 世界风云(world)

统计

【题目描述】

Sponsor 是神,他很会创世,但是他退休了,所以他打开了一款策略游戏。

Sponsor 创建了 $n$ 个国家,下标从 $0$ 开始。他希望世界上所有国家能组建一个世界联盟,即一个包含所有国家的联盟。但是国家 $i$ 只愿意和 $p_i$ 个国家组建联盟,特别的,如果国家 $i$ 愿意和国家 $j$ 组建联盟,那么国家 $j$ 也愿意和国家 $i$ 组建联盟。

国家间组建联盟的过程是:有 $c$ 个国家 $a_1,a_2\dots a_c$ 提议组建一个仅包含当前 $c$ 个国家的联盟,当任意两个国家 $a_i,a_j(i\ne j)$ 愿意结盟,这个联盟可以组建。一个国家可以参加多个联盟。

Sponsor 依然期待着世界联盟的组建,结果在无尽的历史长河里,他发现对于任意国家集合 $S$,当他们想要组建联盟时,至少有一个国家只愿意和 $S$ 中小于 $k$ 个国家结盟,导致联盟难以组建。

Sponsor 急了,他决定利用 ∼ 键直接删除几个国家(也可以不删),使得最后剩下的国家能加入同一个联盟。Sponsor 还是很善良,他希望最大化剩下来的国家的数量。

但是 Sponsor 只是一个神,他希望你能求出这个数。

【简要题意】

对于有 n 个点的有向连通图,有 $p_i$ 条边以点 $i$ 为起点。且如果有边 $x\rightarrow y$,一定有边 $y\rightarrow x$。对于这个图的任意点导出子图,其中至少有一个点的度数小于 $k$。求原图的最大子图,满足这个子图是竞赛图,输出子图点数。

【输入格式】

从文件 world.in 中读入数据。

第一行两个正整数 $n,k$,表示国家数和上文所述 $k$。

接下来 $n$ 行,第 $i+1$ 行由一个整数 $p_i$ 开始,接下来是 $p_i$ 个整数,表示国家 $i-1$ 愿意与哪些国家组建联盟。

【输出格式】

输出到文件 world.out 中。

输出一个整数,表示剩下来的国家数量。

【样例输入】

5 3
2 3 4
2 2 3
3 1 3 4
3 1 2 0
2 2 0

【样例输出】

3

【测试点约束】

每个子任务的具体限制如下: Subtask 1(22 pts):$k\le 2,n\le 5\times 10^3$。 Subtask 2(11 pts):$k\le 3,n\le 5\times 10^3$。 Subtask 3(33 pts):$p_i\le 10$。 Subtask 4(34 pts):无限制。 对于 100% 的数据,$0\le p_i