并查集——按秩合并

想想看自从NOIP2017奶酪那个题以多加一个else被卡到70之后，我在没打过并查集……
有点愧疚呢…
所以就再学一些新的内容啦。
那就是按秩合并！大概就是原来所有元素的秩rank都是1，然后在每次合并操作时，让rk大的元素做rk小的元素的父亲，如果rk一样，则使一个元素做另一个元素的父亲，然后做父亲的元素的rk++。
下面就是代码了：

#include<bits/stdc++.h>
using namespace std;
const int maxn=10001;
int n,m,fa[maxn],x,y,rank[maxn];
inline int read()
{
    int f=1,s=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return f*s;
}
inline int find(int a)
{
    if(fa[a]!=a)return find(fa[a]);
    return fa[a];
}
inline void merg(int a,int b)
{
    a=find(a),b=find(b);
    if(a==b)return;
    if(rank[a]<rank[b])fa[a]=b;
    else 
    {
        fa[b]=a;
        if(rank[a]==rank[b])rank[a]++;
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)fa[i]=i,rank[i]=1;
    while(m--)
    {
        x=read();
        if(x==1)
        {
            x=read();y=read();
            merg(x,y);
        }
        else 
        {
            x=read();y=read();
            if(find(x)==find(y))printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}

带读入优化的代码提交了2次，在没开O2的情况下（开过一次，反而更慢），第一次76ms，第二次108ms。