为什么70啊

P3367 【模板】并查集

cf1416207159 @ 2017-11-08 20:06:59

#include<bits/stdc++.h>
using namespace std;
int n,m;
int fa[10000001];
int unionn(int x,int y);
int find(int x);
int main( )
{
    int i,x,y,z;
    freopen("a.txt","r",stdin);
    cin>>n>>m;
    for(i=1;i<=n;i++)
       {
           fa[i]=i;
       }
    for(i=1;i<=m;i++)
      {
          cin>>z>>x>>y;
          if(z==1)  unionn(x,y);
        if(z==2) 
        {
          if(find(x)==find(y)) cout<<"Y"<<endl;
          else cout<<"N"<<endl;
        }
      }
    return 0;
}
int unionn(int x,int y)
{
    int r1=find(x);
    int r2=find(y);
    fa[r1]=r2;
}
int find(int x)
{
    if(fa[x]==x) return x;
    else return find(fa[x]);
}

by D10s @ 2017-11-08 20:12:57

没有压缩路径啊,把find()里面return find(fa[x])改成return fa[x]=find(fa[x]);


by D10s @ 2017-11-08 20:13:29

@cf1416207159


by cf1416207159 @ 2017-11-08 20:18:24

@D10s 谢谢大佬


|