请问为什么会超时

drewxa7 @ 2024-03-29 17:17:58

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int findRoot(int m,int *a){
    int root=m;
    while(a[root]>0){
        root=a[root];
    }
    if(a[m]>0){
        a[m]=root;
    }
    return root;
}
void merge(int m,int n,int *a){
    int mRoot=findRoot(m,a);
    int nRoot=findRoot(n,a);
    a[mRoot]=nRoot;
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    n++;
    int a[n];
    memset(a,-1,sizeof(a));
    int q[m];
    int qSize=0;
    int z,x,y;
    int r1,r2;
    for(int i=0;i<m;i++){
        scanf("%d %d %d",&z,&x,&y);
        if(z==1){
            merge(x,y,a);
        }
        else{
            r1=findRoot(x,a);
            r2=findRoot(y,a);
            if(r1==r2){
                printf("Y\n");
            }
            else{
                printf("N\n");
            }
        }
    }
}

by wangbinfeng @ 2024-03-29 17:21:39

@drewxa7 合并的时候特判一下，如果已经祖先相同就不合并直接跳过

如果不想这么改，那么参照题解，将祖先预处理为自己

by drewxa7 @ 2024-03-29 17:26:48

@wangbinfeng 感谢解答，第一次用洛谷有点蜜汁自信以为是环境有什么问题，这里真的是疏忽了

by wangbinfeng @ 2024-03-29 17:27:52

@drewxa7 本地和luogu评测有时候还是有点区别的，你可以下载个NOI Linux虚拟机（比较麻烦，不推荐）或者用luogu在线IDE

by drewxa7 @ 2024-03-29 17:29:45

@wangbinfeng ok谢谢，我以后会多用在线ide的

by kjhhjki @ 2024-03-29 19:47:29

考虑一条链，合并完得到这条链过后从下往上依次询问它与根的关系，由于你在 find 过程没有进行沿途所有节点的路径压缩，且 merge 过程也没有带启发式，那么最终的复杂度就会被卡到 O(n^2) 从而得到 TLE

by bu_chi_suan @ 2024-03-31 14:45:08

纯C代码：

#include<stdio.h>
int num[10010];
int arr[200010][3];
int find(int n)
{
    int r=n;
    while(r!=num[r])
        r=num[r];
    return r;
}
void merge(int x,int y)
{
    int fx,fy;
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
        num[fy]=fx;
}
int main()
{
    int N,M;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)
        num[i]=i;
    for(int i=0;i<M;i++)
        scanf("%d%d%d",&arr[i][0],&arr[i][1],&arr[i][2]);
    for(int i=0;i<M;i++)
    {
        if(arr[i][0]==1)
        {
            merge(arr[i][1],arr[i][2]);
        }
        else if(arr[i][0]==2)
        {
            if(find(arr[i][1])==find(arr[i][2]))
                printf("Y\n");
            else
                printf("N\n");
        }
    }
    return 0;
}