看起来没什么问题啊

P3367 【模板】并查集

lele2002 @ 2017-11-07 17:21:34

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[10001];
int l(int p)
{
    if(p==f[p])
        return f[p];
    else
        return l(f[p]);
}
void h(int a,int b)
{
    int x=l(a),y=l(b);
    if(x!=y)
        f[x]=y;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1)
            h(x,y);
        else
            if(l(x)==l(y))
                cout<<'Y'<<endl;
            else
                cout<<'N'<<endl;
    }
}

by VCode @ 2017-11-07 17:25:43

  1. 不推荐这么起变量名与函数名

  2. 不推荐用cin和cout输入输出(string除外)

  3. 没压缩路径


by VCode @ 2017-11-07 17:28:14

int find(int son) {
  if(fa[fa[son]] != fa[son]) {//如果你爸爸的爸爸不是你的爸爸,那你的爸爸就变成你爸爸的爸爸
    fa[son] = find(fa[son]);//压缩路径
  }
  return fa[son];
} 

void join(int a, int b) {
  fa[find(a)] = find(b);
}

|