A6268. 最少学习费用
编程题
普及/提高-
知识点
题目描述
“BerCorp” 公司有 $n$ 名员工。这些员工可以使用 $m$ 种被批准的官方语言进行正式交流。
语言用整数 $1 \sim m$ 编号。
对于每一位员工，我们知道 TA 当前会的语言列表，这个列表可能为空（即有的员工现在不会任何官方语言）。
不过好消息是：员工们都愿意学习新的语言，只要公司替他们付学费。每名员工学习一门语言的费用为 $1$ 伯币，同一个人可以学多门语言，费用按门数累加。
如果两位员工会的语言中有至少一门是相同的，就认为他们可以直接交流。
如果员工 $A$ 可以和员工 $B$ 交流，员工 $B$ 可以和员工 $C$ 交流，那么也认为 $A$ 可以通过 $B$ 间接和 $C$ 交流。
现在，公司想花尽量少的钱，让**任意一位员工都能（直接或间接）与任何其他员工进行交流**。
请你计算公司至少需要花费多少伯币。
语言用整数 $1 \sim m$ 编号。
对于每一位员工，我们知道 TA 当前会的语言列表，这个列表可能为空（即有的员工现在不会任何官方语言）。
不过好消息是：员工们都愿意学习新的语言，只要公司替他们付学费。每名员工学习一门语言的费用为 $1$ 伯币，同一个人可以学多门语言，费用按门数累加。
如果两位员工会的语言中有至少一门是相同的，就认为他们可以直接交流。
如果员工 $A$ 可以和员工 $B$ 交流，员工 $B$ 可以和员工 $C$ 交流，那么也认为 $A$ 可以通过 $B$ 间接和 $C$ 交流。
现在，公司想花尽量少的钱，让**任意一位员工都能（直接或间接）与任何其他员工进行交流**。
请你计算公司至少需要花费多少伯币。
输入格式
第一行包含两个整数 $n$ 和 $m$（$2 \le n,m \le 100$），分别表示员工人数和官方语言的数量。
接下来 $n$ 行，第 $i$ 行描述第 $i$ 位员工现在会的语言：
- 这一行的第一个整数为 $k_i$（$0 \le k_i \le m$），表示第 $i$ 位员工会的语言个数；
- 接下来有 $k_i$ 个整数 $a_{i1}, a_{i2}, \dots, a_{ik_i}$（$1 \le a_{ij} \le m$），表示这些语言的编号。
保证同一名员工的语言列表中不会出现重复的语言编号。
注意，可能存在 $k_i = 0$ 的员工（即目前不会任何官方语言）。
同一行中相邻两个整数之间用一个空格隔开。
接下来 $n$ 行，第 $i$ 行描述第 $i$ 位员工现在会的语言：
- 这一行的第一个整数为 $k_i$（$0 \le k_i \le m$），表示第 $i$ 位员工会的语言个数；
- 接下来有 $k_i$ 个整数 $a_{i1}, a_{i2}, \dots, a_{ik_i}$（$1 \le a_{ij} \le m$），表示这些语言的编号。
保证同一名员工的语言列表中不会出现重复的语言编号。
注意，可能存在 $k_i = 0$ 的员工（即目前不会任何官方语言）。
同一行中相邻两个整数之间用一个空格隔开。
输出格式
输出一个整数，表示为了让任意两名员工都可以（直接或间接）交流所需要花费的最少总费用。
输入输出样例
输入 #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
说明/提示
### 样例解释 #1
五名员工会的语言分别为：
- 员工 $1$：$\{2\}$
- 员工 $2$：$\{2,3\}$
- 员工 $3$：$\{3,4\}$
- 员工 $4$：$\{4,5\}$
- 员工 $5$：$\{5\}$
可以发现，他们通过这些语言本身就已经“串成了一条链”，任意两人之间都可以通过若干中间人间接交流，因此不需要再额外学习语言，答案为 $0$。
### 样例解释 #2
- 员工 $1$：不会任何语言；
- 员工 $2$：$\{1,2,3\}$；
- 员工 $3$：$\{1\}$；
- 员工 $4$：$\{5,4\}$；
- 员工 $5$：$\{6,7\}$；
- 员工 $6$：$\{3\}$；
- 员工 $7$：$\{7,4\}$；
- 员工 $8$：$\{1\}$。
一种可行的最优方案是：
- 让员工 $1$ 学习语言 $2$；
- 让员工 $8$ 学习语言 $4$。
此时所有员工都会被连成一个整体，花费为 $2$，可以证明这是最小值。
### 样例解释 #3
- 员工 $1$：$\{2\}$；
- 员工 $2$：不会任何语言。
只要让员工 $2$ 学习语言 $2$，两人就可以直接交流，花费为 $1$。显然这是最优方案。
五名员工会的语言分别为：
- 员工 $1$：$\{2\}$
- 员工 $2$：$\{2,3\}$
- 员工 $3$：$\{3,4\}$
- 员工 $4$：$\{4,5\}$
- 员工 $5$：$\{5\}$
可以发现，他们通过这些语言本身就已经“串成了一条链”，任意两人之间都可以通过若干中间人间接交流，因此不需要再额外学习语言，答案为 $0$。
### 样例解释 #2
- 员工 $1$：不会任何语言；
- 员工 $2$：$\{1,2,3\}$；
- 员工 $3$：$\{1\}$；
- 员工 $4$：$\{5,4\}$；
- 员工 $5$：$\{6,7\}$；
- 员工 $6$：$\{3\}$；
- 员工 $7$：$\{7,4\}$；
- 员工 $8$：$\{1\}$。
一种可行的最优方案是：
- 让员工 $1$ 学习语言 $2$；
- 让员工 $8$ 学习语言 $4$。
此时所有员工都会被连成一个整体，花费为 $2$，可以证明这是最小值。
### 样例解释 #3
- 员工 $1$：$\{2\}$；
- 员工 $2$：不会任何语言。
只要让员工 $2$ 学习语言 $2$，两人就可以直接交流，花费为 $1$。显然这是最优方案。