题目链接: https://vjudge.net/contest/538552#problem/B

题意

共有 m 种语言，给出 n 个人掌握的语言，如果两个人都会一门相同的语言，那么这两个人可以进行沟通。如果两者没有共同语言，他们可以借助第三者(同时与这两个人有共同语言)进行翻译沟通。

令一个人学习一门新语言的代价为 1。求让这 n 个人可以互相沟通所需的最小代价。

(2 ≤ n, m ≤ 100)

思路

如果有一个群体可以互相沟通，那么新加入的一个人只要与这个群体中的任何一个人有一门共同语言就可以与这个群体进行沟通。

我们把语言和人都分成独立的点。对于一个可以互相沟通的群体而言，令其所有语言和人相连成为一个集合。那么新加进来的人只需要检查它掌握的语言是否位于某个集合中，如果是，那么将他加入这个群体，并将他所有掌握的语言一并加入群体。最后只需要返回(群体的数量-1)。

时间复杂度 O(n·m)。

代码

#include <iostream>
#include <set>

#define orep(i,l,r) for(auto i = (l); i < (r); ++i)
#define NL          '\n';
const int maxN = 2e5+5;

int par[maxN];

int find(const int x) { return x==par[x] ? x : (par[x] = find(par[x])); }

void merge(const int u, const int v) {
  const int x = find(u), y = find(v);
  if (x != y) { par[x] = y; }
}

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(nullptr);
  int n, m; std::cin >> n >> m;
  orep(i, 1, n+m+2) { par[i] = i; }
  int langs = 0;
  orep(i, 0, n) {
    int num; std::cin >> num;
    orep(j, 0, num) {
      int lang; std::cin >> lang; langs += lang;
      merge(lang+n, i+1);
    }
  }
  int ret = 0;
  orep(i, 1, n+1) {
    ret += (find(i) == i);
  }
  std::cout << ret-1+(langs==0);
  return 0;
}