初学并查集，问问dalao怎么TLE了 qwq

diu· @ 2018-11-05 07:40:59

#include<iostream>
#include<cstdio>
#define MAXN 12000 
using namespace std;
int n,m,x,y,z;
int f[MAXN];
int find(int x){return f[x]==x?x:find(f[x]);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++)f[i]=i;
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d%d",&z,&x,&y);
        int t1=find(x);
        int t2=find(y);
        if(z==1){if(t1!=t2)f[t2]=t1;}
        else
        {
            if(t1!=t2)printf("N\n");
            else printf("Y\n"); 
        }
    }
    return 0;
}

int find(int x)
{
    int y = x;
    while(y!=f[y])y = f[y];
    while(x!=f[x])
    {
        int pr = f[x];
        f[pr] = y;x = pr;
    }
    return x;}

by 子谦。 @ 2018-11-05 07:42:34

因为你的递归版没有更新值

by AmlyC @ 2018-11-05 07:43:12

@Coffee·

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

路径压缩不是这样写吗？？

by Oxygen_L @ 2018-11-05 07:44:30

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

by IRipple @ 2018-11-05 07:48:36

并查集要路径压缩的，要把fa[x]换成find(f[x])

by diu· @ 2018-11-05 07:49:52

哦哦~这样嘛，谢谢大佬

by k_z_j @ 2018-11-05 07:51:33

因为你之前的版本没有使用路径压缩，简单来说就是树形态可能被拉成一条链，导致复杂度上升到n^2。

by k_z_j @ 2018-11-05 07:51:50

@Coffee

by diu· @ 2018-11-05 07:52:47

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

可是我这样写还是T掉三个点qwq @BeyondOI

by diu· @ 2018-11-05 07:53:24

0.0

by sdxjzsq @ 2018-11-05 07:58:47

@Coffee· 你合并操作写得不对啊...
看了半天也没找到一个合并操作的函数，原来写主程序里了...
你合并操作的时候，要先找到两个数最靠上的父亲，然后判断父亲是否相等，在合并父亲。
大概长这样：

inline void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return;
    fa[x]=y;
}

加上启发式合并跑得更快...