首页 > 代码库 > poj 1733 Parity game【哈希+并查集】
poj 1733 Parity game【哈希+并查集】
这道题题意我不想说了,但是有一个条件必须的说,就是1-2其实是0-2这条边,3-4是2-4这条边,但是困惑了好久,其他就是哈希给他一个地址 ,然后把注解看下方
#include <stdio.h> #include <string.h> #define maxx 10001 int par[maxx]; int rank[maxx]; void init() { for(int i=0;i<=maxx;i++) { rank[i]=0; par[i]=i; } } int findset(int n) { if(n==par[n]) return n;; int t =findset(par[n]); rank[n]=(rank[n]+rank[par[n]])%2;//判断父亲和儿子的奇偶性,并更新他们 par[n]=t; return par[n]; } int unite(int n,int m,int h) { int pn=findset(n); int pm=findset(m); if(pn==pm) { if((rank[n]+rank[m]+h)%2==0) return 1; else return 0; } else { par[pn]=pm; rank[pn]=(rank[n]+rank[m]+h)%2; return 1; } } int hash[maxx]; int aa=0; int main () { int N; int M; scanf("%d",&N); init(); scanf("%d",&M); int a,b; char s[10]; int hh; int j; for(j=0;j<M;j++) { int px=0,py=0; scanf("%d%d%s",&a,&b,s); if(s[0]=='o') hh=1; else hh=0; a--; hash[0]=0; for(int i=0;i<=aa;i++)//用哈希给他们地址 { if(hash[i]==a) { px=i; break; } } if(px==0&&a!=0) { aa++; hash[aa]=a; px=aa; } for(int i=0;i<=aa;i++) { if(hash[i]==b) { py=i; break; } } if(py==0&&b!=0) { aa++; hash[aa]=b; py=aa; } if(unite(px,py,hh)==0) break; } printf("%d\n",j); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。