#2748. Learning Languages

Learning Languages

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

农夫约翰的N\red{N(}2<=N<=10,000\red{2 <= N<=10,000)}头奶牛,编号为1..N\red{1.. N,}一共会流利地使用M\red{M(}1<=M<=30,000\red{1<= M <=30,000)}种语言,编号从1..M.\red{1 .. M.,}i\red{i}头,会说Ki\red{K_i(}1<=Ki<=M\red{1 <= K_i<= M)}种语言,即Li1,Li2,...,LiKi(1<=Lij<=M)\red{L_{i1}, L_{i2},..., L_{iK_i} (1 <= L_{ij} <= M)}FJ\red{FJ}的奶牛不太聪明,所以Ki\red{K_i}的总和至多为100,000\red{100,000}

两头牛,不能直接交流,除非它们都会讲某一门语言。然而,没有共同语言的奶牛们,可以让其它的牛给他们当翻译。换言之,牛A\red{A}B\red{B}可以谈话,当且仅当存在 一个序列奶牛T1\red{T_1,}T2...\red{T_2,...,}Tk\red{T_k,}A\red{A}T1\red{T_1}都会说某一种语言,T1\red{T_1}T2\red{T_2}也都会说某一种语言……,并且Tk\red{T_k}B\red{B}会说某一种语言。

农夫约翰希望他的奶牛更加团结,所以他希望任意两头牛之间可以交流。他可以买书教他的奶牛任何语言。作为一个相当节俭的农民,FJ\red{FJ}想要购买最少的书籍,让所有他 的奶牛互相可以说话。

帮助他确定:

\red{*}他必须购买的书籍的最低数量

输入格式

1\red{1}行:两个用空格隔开的整数:N\red{N}M\red{M}

2..N+1\red{2.. N +1}行:第i+1\red{i +1}行描述的牛i\red{i}的语言,Ki+1\red{K_{i+1}}个空格隔开的整数:KiLi1\red{K_i ,L_{i1}} Li2...\red{L_{i2},...,}LIKi\red{L_I{K_i}}

输出格式

1\red{1}行:一个整数,FJ\red{FJ}最少需要购买的书籍数量。

样例

输入样例

3 3
2 3 2
1 2
1 1

输出样例

1

提示

给三号牛买第二本书即可

数据结构3

未参加
状态
已结束
规则
IOI
题目
19
开始于
2023-1-9 12:00
结束于
2023-1-17 20:00
持续时间
200 小时
主持人
参赛人数
12