K.分组

题目要意:每次给你一些音符，你需要把这些音符所在的组合并，求最后有多少组

解法并查集

事实上，这是一道并查集的模版题

对于集合合并的题目，我们应该很快想到并查集

但每次给出的点较多，需要把他们两两连成一个集合吗？这样的时间复杂度为，显然无法通过。

事实上，根据并查集的本质，我们只需要把它们全部连到第一个点上即可，这样和两两相连是等价的。

这么做的时间复杂度为，可以通过

以下为出题人的代码

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
	if(x>y) std::swap(x,y);
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
void solve() {
    int n,q;
    cin>>n>>q;
    DSU dsu(n+1);
    int ans=n;
    while(q--)
    {
        int k;
        cin>>k;
        int qq=-1;
        for(int i=1;i<=k;i++)
        {
            int ww;
            cin>>ww;
            if(i==1)
            {
                qq=ww;
            }
            ans-=dsu.merge(qq,ww);
        }
    }
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int __ = 1;
    while (__--) {
        solve();
    }
    return 0;
}

出题人题解

K.分组

解法 并查集

解法并查集