re了三个点求调

P3367 【模板】并查集

az0913 @ 2023-09-08 20:09:12

#include <bits/stdc++.h>
using namespace std;
long long f[1086],n,m,z;
long long   a,b;
int find(int x)
{
    return x==f[x]?x:find(f[x]);
}
void hebing (int x,int y)
{
    int fx,fy;
    fx=find(x);
    fy=find(y);
    f[fx]=fy;
}
int main()
{

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>z>>a>>b;
        if(z==1)
        {
            hebing(a,b);
        }
         if(z==2){
        if(find(a)==find(b)){
                    cout<<"Y"<<endl;
                }
                else {
                    cout<<"N"<<endl;
                }
        }
    }
    return 0;
}

by Untitled_unrevised @ 2023-09-08 20:22:44

f 数组开太小了,题目的 N 最大可以到 10^4 啊。


by Untitled_unrevised @ 2023-09-08 20:25:58

还有这个 find 的复杂度不正确,三个数据点会 TLE。


by az0913 @ 2023-09-08 20:31:21

@Untitled_unrevised 谢谢大佬 过了


|