题目链接:http://codeforces.com/contest/278/problem/C
能够互相交流的放到同一个集合里面,最后有多少个集合,就需要花集合数目-1的钱,因为一个集合中只需要有一个人学会另外一个集合中的任意一个人回的任意一门语言两个集合的人就可以互相交流。
![](/Images/OutliningIndicators/ContractedBlock.gif)
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6 int p[110], n, m, a[110][110], num[110];
7 int find(int x){
8 return p[x] != x ? p[x] = find(p[x]) : x;
9 }
10 int cmp(int a, int b){
11 return a > b;
12 }
13 int main(){
14 while (~scanf("%d%d", &n, &m)){
15 memset(a, 0, sizeof(a));
16 for (int i = 0; i <= n; i++) p[i] = i;
17 for (int i = 0; i < n; i++){
18 scanf("%d", &a[i][0]);
19 for (int j = 1; j <= a[i][0]; j++) scanf("%d", &a[i][j]);
20 }
21 for (int i = 0; i < n; i++)
22 for (int j = 0; j < n; j++)
23 if (j != i){
24 int r1 = find(i), r2 = find(j);
25 if (r1 == r2) continue;
26 else
27 for (int k = 1; k <= a[i][0]; k++)
28 for (int l = 1; l <= a[j][0]; l++)
29 if (a[i][k] == a[j][l]) p[r2] = r1;
30 }
31 int cnt = 0;
32 bool b = 0;
33 for (int i = 0; i < n; i++) if (a[i][0] != 0) b = 1;
34 for (int i = 0; i < n; i++) if (p[i] == i) cnt += 1;
35 int ans = cnt - 1;
36 if (!b) ans = n;
37 printf("%d\n", ans);
38 }
39 return 0;
40