玄关，拜谢

uua___ @ 2024-05-12 14:55:46

#include<bits/stdc++.h>
using namespace std;
int father[500000];

int find(int x)
{
    if(father[x]!=x) return find(father[x]);
    else return x;
}
void unionn(int r1,int r2)
{
    father[r2]=r1;
}

int main()
{
int n,m,i,x,y;cin>>n>>m;

    int z;
for(i=1;i<=n;i++)
{
    father[i]=i;
}
for(i=1;i<=m;i++)
{
    cin>>z>>x>>y;
    int r1=find(x);
    int r2=find(y);
    if(z==1) unionn(r1,r2);

        if(z==2)
        {
            if(find(x)==find(y))
        {
            cout<<"Y"<<endl;
        }
        else
        {
            cout<<"N"<<endl;
        }
        }

}       

    return 0;
}//TLE!!!!!!

by WRuperD @ 2024-05-12 15:05:28

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

by Sun_pirf @ 2024-05-12 15:18:04

查询函数的问题

int find(int x)
{
    if(father[x]!=x) 
            return father=find(father[x]);
    else 
            return x;
}

或

int find(int x)
{
    if(f[x]==x)
        return x;
    return find(f[x]);
}

by masonxiong @ 2024-05-12 15:45:48

@uua___

根本上来说，这个程序没有问题，但是你的并查集是朴素的并查集，单次查询复杂度会被卡到 O(n)

为解决这一问题，有两种方案：

路径压缩

在查询一个节点所在的根时，直接将路径上所有的点的父亲直接指向根，这样再次查询就是 O(1) 的

此外，find 似乎是某个库函数名字，建议改名

实现：

int find_father(int x) {
  if (father[x] == x)
    return x;
  father[x] = find_father(father[x]);
  return father[x];
}

当然可以简写成这样：

int find_father(int x) {
  return father[x] == x ? x : father[x] = find_father(father[x]);
}

可以优化至 O(\log n)

启发式合并

朴素并查集单次查询之所以可能被卡到 O(n) 是因为数据可以把你的树卡成一条链，导致树高 O(n)，单次查询就是 O(n) 的了

为了避免这个问题，在合并两棵树的时候，你可以比较两棵树的树节 点个数，将节点个数多的作为父亲

这个代码懒得写了（

也可以优化到 O(\log n)

如果你同时使用两个优化，查询的平均复杂度是 O(\alpha(n))，\alpha 是反阿克曼函数，增长非常缓慢，不超过 4