POJ 1733 Parity game（种类并查集）

POJ 1733 Parity game（种类并查集）

​​传送门​​

题目大意

输入n表示有一个长度为n的0,1字符串, m表示接下来有m行输入, 接下来的m行输入中x, y, even表示第x到第y个字符中间1的个数为偶数个, x, y, odd表示第x到第y个字符中间1的个数为奇数个, 若m句话中第k+1是第一次与前面的话矛盾, 输出k;

思路

若x, y之间1的个数为偶数个, 那么1~x 与1~y中1的个数同奇偶性, 反之则异奇偶性, 我们可以将其理解为若输入x, y, even, 即x, y属于同种, 反之则属于不同种。输入的数据中x, y是闭区间, 不好处理, 我们可以将其化为半开区间来处理, (x-1, y] 或者 [x, y+1)

代码

int fa[maxn],rank[maxn];int find(int x){ if(fa[x]==x){ return x; } int tmp=find(fa[x]); rank[x]=(rank[x]+rank[fa[x]])%2; return fa[x]=tmp;}mapmp;int Union(int x,int y,int flag){ int fx=find(x); int fy=find(y); if(fx==fy){ if((rank[x]+rank[y])%2!=flag){ return 1; } else{ return 0; } } else{ fa[fx]=fy; rank[fx]=(rank[x]+rank[y]+flag)%2; } return 0;}int main(){ int n,m; int ans=0; scanf("%d%d",&n,&m); for(int i=1;i<=maxn;i++){ fa[i]=i; rank[i]=0;//0 偶数 1奇数 } int q=0; for(int i=1;i<=m;i++){ int x,y; char op[10]; int flag; scanf("%d%d%s",&x,&y,op); if(!mp[x-1]){ mp[x-1]=++q; } if(!mp[y]){ mp[y]=++q; } if(op[0]=='e'){//偶数 flag=0; } else{// 奇数 flag=1; } if(Union(mp[x-1],mp[y],flag)&&!ans){ ans=i; } } if(!ans){ ans=m+1; } printf("%d\n",ans-1);}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。