2019牛客暑期多校訓練營（第九場）All men are brothers——并查集&&組合數

題意

最初有 $n$ 個人且互不認識，接下來 $m$ 行，每行有 $x,y$，表示 $x$ 和 $y$ 交朋友，朋友關系滿足自反性和傳遞性，每次輸出目前選取4個人且互不認識的方案數。

分析

并查集維護集合的并。

考慮兩個集合的并對答案的影響，總的來說就是減去集合x中選一個、集合y中選一個，剩下的選兩個（這兩個來自不同集合）。

代碼實作上體會 $cs$ 變量的作用。

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
const int maxn = 1e5 + 10;
int n, m;
int fa[maxn], rk[maxn];

ll C4(ll x)
{
    return x * (x-1)/2 * (x-2)/3 * (x-3)/4;
}
ll C2(ll x)
{
    return x * (x-1) / 2;
}
void init()
{
    for(int i = 1;i <= n;i++)
    {
        fa[i] = i;
        rk[i] = 1;
    }
}
int find(int x)
{
    if(x != fa[x])  fa[x] = find(fa[x]);
    return fa[x];
}
void unite(int x, int y)
{
    int rx = find(x);
    int ry = find(y);
    if(rx == ry)  return;
    fa[rx] = ry;
    rk[ry] += rk[rx];
}

int main()
{
    scanf("%d%d", &n, &m);
    ll ans = C4(n);
    printf("%lld\n", ans);

    init();

    ll cs = 0;  //每個集合中取兩個的方案數的和
    for(int i = 0;i < m;i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        if(find(a) == find(b))
        {
            printf("%lld\n", ans);
            continue;
        }
        int rka = rk[find(a)], rkb = rk[find(b)];
        ll tmp1 = 1LL * rka * rkb;
        ll tmp2 = C2(n-rka-rkb) - (cs - (C2(rka)+C2(rkb)));
        cs = cs - (C2(rka)+C2(rkb)) + C2(rka+rkb);
        ans -= tmp1 * tmp2;
        printf("%lld\n", ans);
        unite(a, b);
    }
    return 0;
}      

個性簽名：時間會解決一切