← 返回题单
题单练习 广度优先搜索
← 上一题 下一题 →

A5411 | Learning Languages

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

“BerCorp”公司有 $n$ 名员工。这些员工可以使用 $m$ 种被批准的官方语言进行正式通信。语言用整数 $1$ 到 $m$ 编号。对于每位员工，我们知道他掌握的语言列表。这个列表可能为空，也就是说员工可能不懂任何官方语言。但员工们愿意学习任意数量的官方语言，只要公司为他们的课程付费。每名员工学习一门语言的费用为 $1$ 伯币。

请你计算公司需要花费的最少总金额，使得任何一位员工都能够与任何其他员工进行通信（通信可以是间接的，即其他员工可以协助翻译）。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \leq n,m \leq 100$）——员工人数和官方语言数量。

接下来的 $n$ 行，每行描述一名员工掌握的语言。第 $i$ 行以整数 $k_i$ 开头（$0 \leq k_i \leq m$），表示第 $i$ 位员工会的语言数。接下来是 $k_i$ 个整数 $a_{ij}$（$1 \leq a_{ij} \leq m$），表示他会的语言的编号。保证每个列表中的语言编号各不相同。注意，有些员工可能不会任何语言。

同一行的数字用一个空格分隔。

输出格式

输出一个整数，表示使得任何员工都能与其他所有员工通信所需的最少费用。

输入输出样例

输入 #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
C++ 编辑器
输入
输出