有三个测试点运行时出错，求解答

我是星星 @ 2017-08-28 21:38:57

#include<iostream>
using namespace std;
int x,y,z,father[10001],n,m;
int find(int t)    //找祖宗 
{
    if(father[t]!=t) return find(father[t]);  //如果其父亲不是祖宗，就找父亲的父亲，依次递归 
    else return t;   //如果找到了祖宗，就返回祖宗的值 
}
void unionn(int r1,int r2)
{
    father[r2]=r1;     //r2的父亲是r2，即集合r1.r2下的所有元素有一个共有祖宗，r1 
}
int main()
{
     cin>>n>>m;
     for(int i=1;i<=n;i++) father[i]=i;
     for(int i=1;i<=m;i++)
       {
           int r1,r2;
           cin>>z>>x>>y;
           if(z==1)
             {
            r1=find(x);     //r1表示x的祖宗 
               r2=find(y);     //r2表示y的祖宗 
               if(r1!=r2) unionn(r1,r2);
          }   //如果r1不等于r2，就将他们两个集合联立为一个集合 
        else 
            if(find(x)==find(y)) cout<<"Y";  //find【x】表示x的祖宗 
            else  cout<<"N";
       }
     return 0;
}

by MANCHERSTER @ 2017-08-28 22:01:34

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

你改成这样试试。。

by MANCHERSTER @ 2017-08-28 22:02:00

@ 2556937429lq

by MANCHERSTER @ 2017-08-28 22:02:44

@ 2556937429lq 我一直这样写并查集的。。

by 过期薯条 @ 2017-09-01 18:49:04

@2556937429lq 要写启发式合并吧。。。我没写只过了几个点

inline void _union(int x, int y) {
  int fx = getfa(x), fy = getfa(y);
  if (rank[fx] >= rank[fy]) fa[fy] = fx, ++rank[fx];
  else fa[fx] = fy, ++rank[fy];
}

by 我是星星 @ 2017-09-03 08:16:31

@MANCHERSTER 谢谢你的指导

by 我是星星 @ 2017-09-03 08:18:22

@Errorman碩 启发式合并有什么不同呢？

求指导

by 我是星星 @ 2017-09-03 08:25:05

@MANCHERSTER 但是改成你这样还是不对啊。。。。。

by 我是星星 @ 2017-09-03 08:34:38

#include<iostream>
using namespace std;
int x,y,z,father[10001],n,m,p;
int find(int t)    //找祖宗 
{
    if(father[t]!=t) return find(father[t]);  //如果其父亲不是祖宗，就找父亲的父亲，依次递归 
    else return t;   //如果找到了祖宗，就返回祖宗的值 
}
void unionn(int r1,int r2)
{
    father[r2]=r1;     //r2的父亲是r2，即集合r1.r2下的所有元素有一个共有祖宗，r1 
}
int main()
{
     cin>>n>>m;
     for(int i=1;i<=n;i++) father[i]=i;
     for(int i=1;i<=m;i++)
       {
           int r1,r2;
           cin>>z>>x>>y;
           if(z==1)
             {
            r1=find(x);     //r1表示x的祖宗 
               r2=find(y);     //r2表示y的祖宗 
               if(r1!=r2) unionn(r1,r2);
          }   //如果r1不等于r2，就将他们两个集合联立为一个集合 
        else 
            if(find(x)==find(y)) cout<<"Y"<<endl;   //find【x】表示x的祖宗 
            else  cout<<"N"<<endl;
       }
     return 0;
}
超出时间限制了现在是，怎么改进啊

by 过期薯条 @ 2017-09-03 10:41:17

@2556937429lq 启发式合并就是把小的集合并到大的集合里面。

by 过期薯条 @ 2017-09-03 10:44:14

@2556937429lq TLE的话是因为没写路径压缩