1 条题解
-
2
因为会同一种语言的人可以互相交流,而且间接交流也是可以的,那么我们可以把题目转换成求连通块的数量。(显然的,如果这都想不到的话我也帮不了你了)
建图1: 如果一个人会语言,那么我们可以在这个人和这种语言之间连一条边。(注意:人的节点和边的节点编号要区分开)
因为可以间接交流,连好边之后在同一个连通块里的人都是可以互相交流的,那么我们只要加入最少的边使所有点变成一个连通块就好了,那么答案就是连通块的个数减一。
这里要特别注意一下,如果,也就是所有人都是一种语言都不会的话,答案就是,如果继续用前面的连通块算的话,答案会变成。
建图2: 对于每种语言,有若干人都会这种语言,那么就把这些人连在一起。(只要连成连通块就行了,可以是一条链也可以是完全图) 使用并查集。
最后统计连通块的个数减一就是答案。
代码丑陋,请勿模仿~
#include<bits/stdc++.h> using namespace std; int n,m,k; int ans; int u,v; struct aa{ int to,nxt; }p[400009]; int h[200009],len; void add(int u,int v){ p[++len].to=v; p[len].nxt=h[u]; h[u]=len; } bool kk[200009]; bool fk[200009]; void dfs(int u){ kk[u]=1; for(int j=h[u];j;j=p[j].nxt) if(!kk[p[j].to]) dfs(p[j].to); } int main(){ scanf("%d%d%d",&n,&m,&k); if(k==0){ printf("%d",n); return 0; } for(int j=1;j<=k;j++){ scanf("%d%d",&u,&v); add(u,n+v+1); add(n+v+1,u); } for(int j=1;j<=n;j++) if(!kk[j]){ ans++; dfs(j); } printf("%d",ans-1); return 0; }
- 1
信息
- ID
- 192
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 304
- 已通过
- 44
- 上传者