#P3262. Learning Languages

    ID: 3262 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>图论图的遍历数据结构并查集连通块CodeForces

Learning Languages

题目描述

BerCorp 公司有 nn 名雇员。这些雇员共掌握 mm 种官方语言(以从 11mm 的整数编号)用于正式交流。对于每个雇员,我们有一个他掌握的语言列表,列表可以为空,这意味着一个雇员可能不掌握任何官方语言。但是雇员们愿意学习语言,只要公司为课程付费。每名雇员学习一种语言需要花费 11 Ber 元。

请找出能让所有雇员直接或间接(可由其他雇员提供中间翻译)交流的最小花费。

输入格式

第一行为两个整数 n,m (2n,m100)n,m\ (2\le n,m\le 100),为雇员的数量和语言的数量。

接下来 nn 行,每行首先有一个整数 ki (0kim)k_i\ (0\le k_i\le m),为雇员 ii 掌握的语言数量,接下来有 kik_i 个整数,为雇员 ii 掌握的语言。这意味着一个表中所有的编号都不同。注意一个雇员可能掌握 00 种语言。

每行中的数字都用一个空格隔开。

输出格式

一个整数,表示能让所有雇员直接或间接交流的最小花费。

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