大佬帮忙看下 为什么全MLE啊

张小花 @ 2019-08-22 20:54:41

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 10010;

struct Node
{
    int father, size;
};

Node trees[MAX_N];
int n, m;
int x, y, z, x_root, y_root;

int find_root(int index)
{
    if (trees[index].father == -1)
    {
        return index;
    }
    int root = find_root(trees[index].father);
    trees[index].father = root;
    return root;
}

void merge(int root1, int root2)
{
    if (trees[root1].size < trees[root2].size)
    {
        trees[root1].father = root2;
        trees[root2].size += trees[root1].size;
    }
    else
    {
        trees[root2].father = root1;
        trees[root1].size += trees[root2].size;
    }
}

int main()
{
    cin >> n >> m;
    Node node;
    node.size = 1;
    node.father = -1;
    for (int i = 1; i <= n; i++)
    {
        trees[i] = node;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> z >> x >> y;
        x_root = find_root(x);
        y_root = find_root(y);
        if (z == 1)
        {
            merge(x_root, y_root);
        } 
        else
        {
            if (x_root == y_root)
            {
                cout << "Y" << endl;
            }
            else
            {
                cout << "N" << endl;
            }
        }
    }
    return 0;
}

by Null_Cat @ 2019-08-22 20:56:08

@张小花 您确定您这是写的并查集。。。。感觉好乱qwq

by End_donkey @ 2019-08-22 20:56:40

假并查集

by 0nullptr @ 2019-08-22 20:56:49

@张小花 为什么不试试路径压缩呐

by Null_Cat @ 2019-08-22 20:57:20

@张小花 w的AC代码：

#include<cstdio>
#define re register
using namespace std;
int fP(int,int[]);
int main(){
    int *n=new int;
    int *m=new int;
    scanf("%d%d",n,m); 
    int *p=new int[*n+1];
    int *a=new int;
    int *cmd=new int;
    int *b=new int;
    for(int i=1;i<=*n;i++) p[i]=i;
    for(int i=1;i<=*m;i++){
        scanf("%d%d%d",cmd,a,b);
        if(*cmd==1){
            p[fP(*a,p)]=fP(*b,p);
        }
        else if(*cmd==2){
            if(fP(*a,p)==fP(*b,p)) putchar('Y');
            else putchar('N');
            putchar('\n');
        }
    }
    delete n;
    delete m;
    delete cmd;
    delete a;
    delete b;
    delete[] p;
    return 0;
}
int fP(int a,int b[]){
    if(a==b[a]) return a;
    else return b[a]=fP(b[a],b);
}

其实并查集的话只需要把查询弄成函数就够了qwq

by muyang_233 @ 2019-08-22 20:57:51

这个并查集好草啊
一般不得把父结点在初始化时设为自己吗

by Null_Cat @ 2019-08-22 20:58:27

@muyang_233 可以设-1的，只不过是设自己更常用。。。

by End_donkey @ 2019-08-22 20:58:49

@张小花

可能初始化有点问题

放下我的码

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[10010];
int k,u,v;
int find(int x){
    if(fa[x]==x) return x;
    else return fa[x]=find(fa[x]);
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=m;++i){
        scanf("%d %d %d",&k,&u,&v);
        if(k==1){
            int fa1=find(u);
            int fa2=find(v);
            fa[fa1]=fa2;
        }
        else{
            int fa1=find(u);
            int fa2=find(v);
            if(fa1==fa2) printf("Y\n");
            else printf("N\n");
        }
    }

    return 0;
}

by Null_Cat @ 2019-08-22 20:59:27

@张小花 而且并查集不用树存储就行。。。只需要开一个parent数组存所在集合的代表元素即可qwq

by Null_Cat @ 2019-08-22 21:02:21

@张小花 另外合并到那个都无所谓，所以个人感觉是因为多开了一个size的缘故，这个size其实根本不需要

by wkywkywky @ 2019-08-22 21:07:52

@张小花 应该是dfs爆栈了

把

 merge(x_root, y_root);

改为

 if(x_root！=y_root)merge(x_root, y_root);