[Luogu] 并查集维护个数 P2078 朋友

(并查集 维护 集合元素个数 模板题)

题意

两个公司 (全是同性别的人)

也就是一个公司 如果有男生 就不可能有 女生

问你 在 小明(1代表) 和 小红 (-1代表 女生都用负数) 认识的人中

最可能凑出来几对情侣(包括他们自己)

吐槽 本来以为是组合数问题 结果 画了一下关系图 就发现 凑出来的情侣数由 认识少的那一方 限制 (那么问题 就简单了 )

步骤

这不就是 并查集 维护 集合中元素的个数 问题嘛

• 那我们要怎么 维护 并查集集合中的 个数呢
• (其实很简单 我们只要加一个 size数组即可 在每次合并的操作的时候 我们直接相加即可)

当然在初始化的时候 每个size[i]都要初始化为1 毕竟 本身也算嘛

if(fa!=fb)
{
    p[fa] = fb;
    sz[fb] +=sz[fa];
}

所以 其他步骤就简单了 就妥妥的 并查集操作即可

CODE

#include 
#define IOS  ios::sync_with_stdio(false)
using namespace std;
const int N = 4e6+10;
int p[N],pm[N];
int n,m,x,q;
int sz[N],szm[N];

int find(int x)
{
    if(x != p[x])
    return p[x] = find(p[x]);
    return p[x];
}
int findm(int x)
{
    if(x != pm[x])
    return pm[x] = findm(pm[x]);
    return pm[x];
}

void init()
{
    for(int i=1; i>n>>m>>x>>q;
    init();

    for(int i=1; i>a>>b;
        int fa = find(a);
        int fb = find(b);

        if(fa!=fb)
        {
            p[fa] = fb;
            sz[fb] +=sz[fa];
        }
    }
    for(int i=1; i>a>>b;
        a=-a, b=-b;
        int fa = findm(a);
        int fb = findm(b);

        if(fa!=fb)
        {
            pm[fa] = fb;
            szm[fb]+=szm[fa];

        }
    }


    int fa = find(1);
    int fb = findm(1);

    int ans = min(sz[fa],szm[fb]);
    cout