1 条题解

  • 2
    @ 2023-10-16 2:23:36

    因为会同一种语言的人可以互相交流,而且间接交流也是可以的,那么我们可以把题目转换成求连通块的数量。(显然的,如果这都想不到的话我也帮不了你了)

    建图1: 如果一个人uu会语言vv,那么我们可以在uu这个人和vv这种语言之间连一条边。(注意:人的节点和边的节点编号要区分开

    因为可以间接交流,连好边之后在同一个连通块里的人都是可以互相交流的,那么我们只要加入最少的边使所有点变成一个连通块就好了,那么答案就是连通块的个数减一。

    这里要特别注意一下,如果k=0k=0,也就是所有人都是一种语言都不会的话,答案就是nn,如果继续用前面的连通块算的话,答案会变成n1n-1

    建图2: 对于每种语言vv,有若干人都会这种语言,那么就把这些人连在一起。(只要连成连通块就行了,可以是一条链也可以是完全图) 使用并查集。

    最后统计连通块的个数减一就是答案。

    代码丑陋,请勿模仿~

    #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
    上传者