题目链接

思路如下

这题可以普通的并查集来做，我们把每个人认识的红娘，放到一个同一个集合里面，然后通过 for循环遍历出现过的编号，看总共有几个集合，当集合的个数大于1的时候，需要的话费rmb的数量是集合数 - 1 ；；其次我们还需要特殊考虑：那些一个红娘都不认识的人，那么他一定要花费1 rmb

题解如下

#include<iostream>

#include<map>

using namespace std;

const int Len = 1005;

int ar[Len];

int find(int x)

{

    if(ar[x] == x)

        return x;

    return ar[x] = find(ar[x]);

}

void Union(int x, int y)

{

    int fx = find(x);

    int fy = find(y);

    if(fx != fy)

        ar[fx] = fy;

}

int main()

{

    map<int,int> mp;

    int m,n;

    scanf("%d %d",&m,&n);

    //初始话集合

    for(int i = 1; i <= n; i ++)

       ar[i] = i;

    int val,first_val;

    int ans = 0;

    for(int i = 1; i <= m; i ++)

    {

        int t;

        scanf("%d",&t);

        if(t == 0)

        {

            ans ++;

        }

        for(int j = 1; j <= t; j ++)

        {

            scanf("%d", &val);

            mp[val] ++;

            if(j == 1)

                first_val = val;

            else

                Union(val , first_val);

        }

    }

    int tem = 0;

    for(auto x:mp)

        if(find(x.first) == x.first)

            tem ++;

    if(tem > 0)

        tem --;

    printf("%d",ans + tem);

    return 0;

}

巴特西

CodeForces 277A 红娘问题（并查子集）

题目链接

思路如下

题解如下

最新文章

热门文章