为何种类并查集在合并时对同类与异类的判断取与可以AC,但取或就WA80pts?
查看原帖
为何种类并查集在合并时对同类与异类的判断取与可以AC,但取或就WA80pts?
1070708
Caged_Bird楼主2024/11/10 23:58

RT,可能是本人对种类并查集理解不够透彻,有没有大佬解释一下?

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,fa[10005],m,tmp[10005],tot;
struct query{
    int x,y,op;
}q[10005];
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
inline void print(int n){if(n<0){putchar('-');print(-n);return;}if(n>9)print(n/10);putchar(n%10+'0');}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int u,v;
        string s;
        cin>>u>>v>>s;
        q[i].x=u-1;
        q[i].y=v;
        if(s=="even")q[i].op=0;
        else q[i].op=1;//1不同,0相同
        tmp[++tot]=q[i].x;
        tmp[++tot]=q[i].y;
    }
    sort(tmp+1,tmp+1+tot);
    tot=unique(tmp+1,tmp+1+tot)-tmp-1;
    for(int i=1;i<=m;i++){
        q[i].x=lower_bound(tmp+1,tmp+1+tot,q[i].x)-tmp;
        q[i].y=lower_bound(tmp+1,tmp+1+tot,q[i].y)-tmp;
    }
    for(int i=1;i<=2*m;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        if(q[i].op==0){
            int fx=find(q[i].x),fy=find(q[i].y),ffx=find(q[i].x+tot),ffy=find(q[i].y+tot);
            if(fy==ffx||fx==ffy){//here wrong
                cout<<i-1;
                return 0;
            }
            if(fx!=fy)fa[fx]=fy;
            if(ffx!=ffy)fa[ffx]=ffy;
        }
        if(q[i].op==1){
            int fx=find(q[i].x),fy=find(q[i].y),ffx=find(q[i].x+tot),ffy=find(q[i].y+tot);
            if(fx==fy||ffx==ffy){//here wrong
                cout<<i-1;
                return 0;
            }
            if(fx!=ffy)fa[fx]=ffy;
            if(fy!=ffx)fa[fy]=ffx;
        }
    }
    cout<<m;
    return 0;
}//WA80pts

两处here wrong||改为&&即可AC

2024/11/10 23:58
加载中...