分析：带权并查集，就是维护一堆关系
然后就是带权并查集的三步
1：首先确定权值数组，sum[i]代表父节点到子节点之间的1的个数（当然路径压缩后代表到根节点的个数）
1代表是奇数个，0代表偶数个
2：设计路径压缩算法 sum[x]=(sum[x]+sum[t])%2;
3：弄清合并根节点时的操作，小的在上；
注：这个题需要离散化
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int N=5e3+5; struct Node{int l,r,v; }p[N]; int a[N<<1],cnt; char s[10]; int fa[N<<1],sum[N<<1]; int find(int x){if(x==fa[x])return x;int t=fa[x];fa[x]=find(fa[x]);sum[x]=(sum[x]+sum[t])%2;return fa[x]; } int main() {int n;while(~scanf("%d%d",&n,&n)){cnt=0;for(int i=1;i<=n;++i){scanf("%d%d%s",&p[i].l,&p[i].r,s);if(s[0]=='e')p[i].v=0;else p[i].v=1;--p[i].l;a[++cnt]=p[i].l,a[++cnt]=p[i].r; }sort(a+1,a+1+cnt);cnt=unique(a+1,a+1+cnt)-a-1;for(int i=0;i<=cnt;++i)fa[i]=i,sum[i]=0;int ans=0;for(int i=1;i<=n;++i){p[i].l=lower_bound(a+1,a+1+cnt,p[i].l)-a;p[i].r=lower_bound(a+1,a+1+cnt,p[i].r)-a;int u=find(p[i].l),v=find(p[i].r);if(u==v){if((2-sum[p[i].r]-sum[p[i].l])%2!=p[i].v)break;}else if(u<v){fa[v]=u;sum[v]=sum[p[i].r]-sum[p[i].l]-p[i].v;}else{fa[u]=v;sum[u]=sum[p[i].l]-sum[p[i].r]+p[i].v;}++ans;}printf("%d\n",ans);}return 0; }
