GDUT_专题三：B - Learning Languages

 题目：

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

Input

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 ki (0 ≤ ki ≤ m) — the number of languages the i-th employee knows. Next, the i-th line contains ki integers — aij (1 ≤ aij ≤ 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.

Output

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

Examples

Input

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

Output

0

Input

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

Output

2

Input

2 2
1 2
0

Output

1

Note

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.

题意：

有 n 个人,m 种语言.给出每个人会的语言 （也可能一种都不会），问最少让几个人学语言,可以使得大家可以互相沟通.

这道题主要考察查并集的应用：

思路：

说实话一开始并没有什么思路，并且虽然题目要求了m种语言，但是题目只要求员工只需要能相互交流就行，并不需要会全部语言。为此还纠结了许久。。。话不多说我们开始正题。

对于一种语言都不会的人，起码得让他学会一种语言才能让他与其他员工沟通，为此我们就需要起码为他花费一美元，之后对其他会语言的员工，我们需要把能沟通的员工放在一个集合里面，所以我们就需要把他们合并，这里就需要用到查并集的知识了。为了要找到能沟通的员工，我们就需要借助语言来记录他们能否沟通了，所以我们需要开一个数组来记录相应下标的语言标识来存放会这门语言的员工的标号。最后在循环判断还有其他未连通的连通块，为了将他们连通也需要花费1美元去学习已连通的一门语言，所以基本上思路就出来了，具体可以看代码注释。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int f[110];//父节点
int v[110];//记录会这么语言的人的编号
int _find(int x) {
	if (x != f[x]) f[x] = _find(f[x]);
	return f[x];
}
void teget(int x, int y) {
	int fx = _find(x);
	int fy = _find(y);
	if (fx != fy)f[fx] = fy;
}

int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) f[i] = i;
	for (int i = 1; i <= n; i++) {
		int k;
		cin >> k;
		if (!k) {//如果一门语言都不会， 起码要学一门语言才能连通
			f[i] = 0;//标记其父节点为0，表示其不会语言
			ans++;
		}
		while (k--) {
			int a;
			cin >> a;//语言的标识
			if (v[a]) {
				teget(v[a], i); //如果这么语言有其他人会，就把他们合并。
				continue;
			}
			v[a] = i; //没人会就记录第i个人会了。
		}
	}
	if (ans == n) { //特判如果全部不会语言就每人起码学一种才能交流
		cout << n << endl;
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		if (f[i] == i)ans++;//这是判断有会语言但是没连通的人的数量，他们需要学会一种已连通的语言才能交流
	}
	cout << ans - 1 << endl;//-1是减去根结点的判定
	return 0;
}