并查集的查询优化

2023/6/14 C++ 算法竞赛 并查集 查询优化

debug了一下午，代码重写了好几遍，最后发现原来是并查集没加查询优化😀，焯！

某一道题

题面

一开始用并查集的时候有想着得加优化不然会被卡，但真出问题了竟然一直在想代码哪里写错了，一直在查循环条件。。

未加优化代码(TLE)：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
const int N=1e5+5;
struct arc
{
    int a,b,w;
}a[N];
int f[N];
vector<int>q[N];
bool cmp(arc x,arc y){return x.w<y.w;}
int find(int x)
{
    return x==f[x]:x:find(f[x]);
}
void merge(int x,int y)
{
    x=find(x);y=find(y);
    if(x!=y)
        f[x]=y;
}
bool judge(int x)
{
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=x;i++)
        merge(a[i].a,a[i].b);
    for(int i=1;i<=k;i++)
    {
        int now=find(q[i][0]);
        for(auto x:q[i])
            if(find(x)!=now)
                return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i].a>>a[i].b>>a[i].w;
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        for(int j=1;j<=x;j++)
        {
            int y;
            cin>>y;
            q[i].push_back(y);
        }
    }
    sort(a+1,a+1+m,cmp);
    int l=1,r=m,ans=m;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))
        {
            ans=mid;
            r=mid;
        }
        else
            l=mid+1;
    }
    cout<<a[ans].w<<'\n';
    return 0;
}

加了优化的代码(AC)：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
const int N=1e5+5;
struct arc
{
    int a,b,w;
}a[N];
int f[N];
vector<int>q[N];
bool cmp(arc x,arc y){return x.w<y.w;}
int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
void merge(int x,int y)
{
    x=find(x);y=find(y);
    if(x!=y)
        f[x]=y;
}
bool judge(int x)
{
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=x;i++)
        merge(a[i].a,a[i].b);
    for(int i=1;i<=k;i++)
    {
        int now=find(q[i][0]);
        for(auto x:q[i])
            if(find(x)!=now)
                return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i].a>>a[i].b>>a[i].w;
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int x;
        cin>>x;
        for(int j=1;j<=x;j++)
        {
            int y;
            cin>>y;
            q[i].push_back(y);
        }
    }
    sort(a+1,a+1+m,cmp);
    int l=1,r=m,ans=m;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))
        {
            ans=mid;
            r=mid;
        }
        else
            l=mid+1;
    }
    cout<<a[ans].w<<'\n';
    return 0;
}

就差了一行代码，复杂度却差了很多。

当谨记这次的惨痛教训

int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}
img_show