题解 CF277A 【Learning Languages】

考虑用并查集维护 为什么是这样呢，题意说的很清楚，相当于是给很多块连边，求最少的数量。那我们就把会同一种语言的放进一个大块中，最后得到 $tot$ 个块就需要 $tot-1$ 条边了 我们具体来分析一下合并的问题。首先没有必要存 $n$ 个人的信息，我们最多只需要 $m$ 个代表，说明有多少不同的语言是**必须**学的。假设 $n$ 个人每个人会的都不同，那就必须有 $n-1$ 个语言得学。每进来一个人，只要会之前存在过的语言就并到那个语言集中，每**成功合并一次**就 $ans--$ 另外还有一个大坑就是如果 $n$ 个人没一个会说话就得学 $n$ 个语言 代码: ```cpp #include <bits/stdc++.h> using namespace std; #define N 103 int n, res; int vis[N]; //vis[i]记录着会第i种语言的人的编号(1<=i<=n) //也是指上文中的“代表” bool NA; //记录特殊情况(是否需要学n种语言) struct unionFindSet { int fa[N]; inline void clear() { for(int i=1; i<=n; ++i) fa[i]=i; return ; } int find(int x) { if(fa[x] == x) return x; return fa[x]=find(fa[x]); } inline void unite(int x, int y) { int fx=find(x), fy=find(y); if(fx != fy) fa[fx]=fy, --res; //注意必须是成功合并一次才ans-- return ; } } T; int main(void) { scanf("%d%*d", &n); T.clear(); res=n-1; //把ans赋初值，就是最多需要的语言数 for(int i=1; i<=n; ++i) { int cnt, x; scanf("%d", &cnt); if(cnt && !NA) NA=true; //如果有一个人会说话，就不需要n种语言 while(cnt--) { scanf("%d", &x); if(vis[x]) T.unite(vis[x], i); else vis[x]=i; } } printf("%d", NA ? res : n); //最后判断一下就好了 return 0; } ```