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