CF277A.Learning Languages

普及/提高-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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).

“BerCorp”公司共有 nn 名员工。这些员工可以使用 mm 种经批准的官方语言进行正式通信。这些语言用从 11 到 mm 的整数编号。对于每名员工,我们已知其掌握的语言列表;该列表可能为空,即某名员工可能不掌握任何官方语言。但员工愿意学习任意数量的官方语言,只要公司为其支付培训费用。每名员工学习一门语言的课程费用为 1 贝尔美元(berdollar)。

请计算公司所需的最小花费总额,使得任意两名员工之间均能进行通信(通信可以是间接的,即其他员工可协助翻译)。

输入格式

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.

第一行包含两个整数 nn 和 mm(2≤n,m≤1002 \leq n, m \leq 100)—— 分别表示员工人数和语言种数。

接下来是 nn 行,每行描述一位员工掌握的语言列表。第 ii 行开头是一个整数 kik_i(0≤ki≤m0 \leq k_i \leq m)—— 表示第 ii 位员工掌握的语言数量;随后是 kik_i 个整数 aija_{ij}(1≤aij≤m1 \leq a_{ij} \leq m)—— 表示该员工掌握的语言编号。保证同一行中所有编号互不相同。注意:某位员工可能一种语言都不掌握。

每行中的数字以单个空格分隔。

输出格式

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.

在第二个样例中,员工 1 可以学习语言 2,员工 8 可以学习语言 4。

在第三个样例中,员工 2 必须学习语言 2。

输入解题思路,AI测评打分。不知道怎么写?

首页