打个板子复习,竟发现了不科学之事

P3367 【模板】并查集

Trinity @ 2018-11-02 09:17:23

在合并时,为什么先判了两者是否在同一集合内错了,难道不是在同一集合内没必要合并吗?

#include <bits/stdc++.h>
#define LL long long
#define inf 2147483647
#define N 300001
using namespace std;
inline LL read(){
    LL f=1,x=0;char ch;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
int n,m,fa[N];
inline void makef(int siz){for(int i=1;i<=siz;i++)fa[i]=i;}
int findf(int u){return fa[u]==u?u:fa[u]=findf(fa[u]);}
void mergef(int u,int v){
    int fu=findf(u),fv=findf(v);
    if(fu!=fv)/*不科学*/fa[fv]=fu;
}
int main(){
    n=read(),m=read();
    makef(n);
    while(m--){
        int opt=read(),u=read(),v=read();
        if(opt==1)mergef(u,v);
        else printf(findf(u)==findf(v)?"Y\n":"N\n");
    }
    return 0;
}

by soul_M @ 2018-11-02 09:25:56

有趣


by Juanzhang @ 2018-11-02 09:32:32

怕不是其他什么写挂了


by soul_M @ 2018-11-02 09:33:03

这就鬼了,为什么我交你的70分代码就A了呢

评测结果


|