301469: CF277A. Learning Languages

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Learning Languages

题意翻译

#### 描述 BerCorp公司有n名雇员。这些雇员共掌握m种官方语言(以从1到m的整数编号)用于正式交流。对于每个雇员,我们有一个他掌握的语言列表,列表可以为空,这意味着一个雇员可能不掌握任何官方语言。但是雇员们愿意学习语言,只要公司为课程付费。每名雇员学习一种语言需要花费 1 Ber元。 请找出能让所有雇员直接或间接(可由其他雇员提供中间翻译)交流的最小花费。 #### 输入 第一行为两个整数n,m(2<=n,m<=100),为雇员的数量和语言的数量。 接下来n行,每行首先有一个整数ki(0<=ki<=m),为雇员i掌握的语言数量,接下来有ki个整数,为雇员i掌握的语言。这意味着一个表中所有的编号都不同。注意一个雇员可能掌握0种语言。 每行中的数字都用一个空格隔开。 #### 输出 一个整数——能让所有雇员直接或间接交流的最小花费。 感谢 @Nishikino_Maki 提供的翻译。

题目描述

The "BerCorp" company has got $ n $ employees. These employees can use $ m $ approved official languages for the formal correspondence. The languages are numbered with integers from $ 1 $ to $ m $ . For each employee we have the list of languages, which he knows. This list could be empty, i. e. an employee may know no official languages. But the employees are willing to learn any number of official languages, as long as the company pays their lessons. A study course in one language for one employee costs $ 1 $ berdollar. Find the minimum sum of money the company needs to spend so as any employee could correspond to any other one (their correspondence can be indirect, i. e. other employees can help out translating).

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 2<=n,m<=100 $ ) — the number of employees and the number of languages. Then $ n $ lines follow — each employee's language list. At the beginning of the $ i $ -th line is integer $ k_{i} $ ( $ 0<=k_{i}<=m $ ) — the number of languages the $ i $ -th employee knows. Next, the $ i $ -th line contains $ k_{i} $ integers — $ a_{ij} $ ( $ 1<=a_{ij}<=m $ ) — the identifiers of languages the $ i $ -th employee knows. It is guaranteed that all the identifiers in one list are distinct. Note that an employee may know zero languages. The numbers in the lines are separated by single spaces.

输出格式


Print a single integer — the minimum amount of money to pay so that in the end every employee could write a letter to every other one (other employees can help out translating).

输入输出样例

输入样例 #1

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

输出样例 #1

0

输入样例 #2

8 7
0
3 1 2 3
1 1
2 5 4
2 6 7
1 3
2 7 4
1 1

输出样例 #2

2

输入样例 #3

2 2
1 2
0

输出样例 #3

1

说明

In the second sample the employee $ 1 $ can learn language $ 2 $ , and employee $ 8 $ can learn language $ 4 $ . In the third sample employee $ 2 $ must learn language $ 2 $ .

Input

题意翻译

#### 描述 BerCorp公司有n名雇员。这些雇员共掌握m种官方语言(以从1到m的整数编号)用于正式交流。对于每个雇员,我们有一个他掌握的语言列表,列表可以为空,这意味着一个雇员可能不掌握任何官方语言。但是雇员们愿意学习语言,只要公司为课程付费。每名雇员学习一种语言需要花费 1 Ber元。 请找出能让所有雇员直接或间接(可由其他雇员提供中间翻译)交流的最小花费。 #### 输入 第一行为两个整数n,m(2<=n,m<=100),为雇员的数量和语言的数量。 接下来n行,每行首先有一个整数ki(0<=ki<=m),为雇员i掌握的语言数量,接下来有ki个整数,为雇员i掌握的语言。这意味着一个表中所有的编号都不同。注意一个雇员可能掌握0种语言。 每行中的数字都用一个空格隔开。 #### 输出 一个整数——能让所有雇员直接或间接交流的最小花费。 感谢 @Nishikino_Maki 提供的翻译。

加入题单

上一题 下一题 算法标签: