首页 > 代码库 > POJ1733 - Parity game - 并查集
POJ1733 - Parity game - 并查集
这道题是带权并查集,只需要把权设成0或1就行,分别表示与根节点的关系。因为10亿个点,所以要用到离散化
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; int p[10005]; int dis[10005]; int ran[10005]; int tot; struct num { char oe[10]; int st,ed; int id; }po[5005]; int find(int n) { int item; if(p[n]!=n) { item=p[n]; p[n]=find(p[n]); ran[n]=(ran[n]+ran[item])%2; } return p[n]; } int half(int node) { int mid; int tail=tot-1; int head=0; while(head<=tail) { mid=(tail+head)/2; if(dis[mid]==node) { return mid; } else if(dis[mid]>node) { tail=mid-1; } else { head=mid+1; } } return -1; } int main() { int n; while(scanf("%d",&n)!=EOF) { int m; scanf("%d",&m); tot=0; for(int i=0;i<m;i++) { po[i].id=i; scanf("%d%d%s",&po[i].st,&po[i].ed,po[i].oe); po[i].st--; dis[tot++]=po[i].st; dis[tot++]=po[i].ed; } //离散化 sort(dis,dis+tot); tot=unique(dis,dis+tot)-dis; for(int i=0;i<=tot;i++) { p[i]=i; ran[i]=0; } int ans=0; for(int i=0;i<m;i++) { int st=half(po[i].st); int ed=half(po[i].ed); int ps=find(st); int pe=find(ed); if(ps==pe) { if(ran[st]==ran[ed]&&po[i].oe[0]=='o') { break; } if(ran[st]!=ran[ed]&&po[i].oe[0]=='e') { break; } ans++; } else { if(po[i].oe[0]=='o') { p[ps]=pe; ran[ps]=((ran[st]+ran[ed])%2+1)%2; } else { p[ps]=pe; ran[ps]=(ran[st]+ran[ed])%2; } ans++; } } printf("%d\n",ans); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。