A. Learning Languages (联通块)

 1 #include <cstdio>
 2 #include <string>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <string.h>
 6 #include <math.h>
 7 #include <vector>
 8  
 9 using namespace std;
10  
11 int vis[105];
12 int mapp[105][105];
13 int a[105][105];
14 int n,m,k,val;
15  
16 void dfs(int i)
17 {
18     vis[i] = 1;
19     for (int j=1;j<=n;j++)
20     {
21         if (!vis[j] && mapp[i][j])
22             dfs(j);
23     }
24 }
25  
26 int main()
27 {
28     int tot = 0;
29     int ans = 0;
30     cin >> n >> m;
31     for (int i=1;i<=n;i++)
32     {
33         cin >> k;
34         if (k == 0)
35             tot++;
36         while (k--)
37         {
38             cin >> val;
39             a[i][val] = 1;
40         }
41     }
42     for (int i=1;i<=n;i++)
43     {
44         for (int j=i+1;j<=n;j++)
45         {
46             for (int o=1;o<=m;o++)
47             {
48                 if (a[i][o] && a[j][o])
49                     mapp[i][j] = mapp[j][i] = 1;
50             }
51         }
52     }
53     for (int i=1;i<=n;i++)
54     {
55         if (!vis[i])
56         {
57             ans++;
58             dfs(i);
59         }
60     }
61     if (tot == n)
62         printf("%d\n",n);
63     else
64         printf("%d\n",ans-1);
65     return 0;
66 }
67