POJ - 1703Find them, Catch them (并查集)

xiaoxiao2021-02-28  7

                  POJ - 1703  Find them, Catch them (并查集)

        这道题与食物链那一道题是同一类型的,但稍微简单些           

        比普通的并查集多了一个relation [i]数组,记录与父亲节点的关系,在并查集里的元素都是已经它们之间的关系的,在路径压缩集合合并时不断的更新relation数组

       r[i]=0代表与父节点同类,r[i]=1代表异类,初始化为同类

      下面推导如何在路径压缩时更新关系:

      根据子节点与父亲节点的关系和父节点与爷爷节点的关系,推导子节点与爷爷节点的关系

  枚举出来所有情况,找出规律(r1+r2)%2或者 r1==r2? 0:1

(a, b) (b, c) (a, c) (r1+r2)%2 0 0 0 0 a 和 b是同类 , b 和 c 是同类, 所以 a 和 c 也是同类 0 1 1 1 a 和 b是同类 , b 和 c 是异类, 所以 a 和 c 也是异类 1 0 1 1 a 和 b是异类 , b 和 c 是同类, 所以 a 和 c 是异类 1 1 0 0 a 和 b是异类 , b 和 c 是异类, 所以 a 和 c 是同类 在集合合并时也可以枚举,同样用矢量运算也可以求得 #include<stdio.h> const int MAXN=100005; int pre[MAXN],re[MAXN]; int n,m; int ans; void init() { for(int i=1;i<=n;i++){ pre[i]=i; re[i]=0;//初始时父节点为本身,当然同类,初始为0 } } int find(int x) //找根节点 { if(x!=pre[x]){ int t=pre[x]; //记录下父亲节点,方便以下更新 pre[x]=find(pre[x]);//根据子节点与父亲节点的关系和父节点与爷爷节点的关系,推导子节点与爷爷节点的关系 r[x] = (r[x]+r[t])%2; ; } return pre[x]; } void merge(int x,int y) { //找到x与y的根节点 int fx=find(x); int fy=find(y); if(fx!=fy){ pre[fy]=fx;//合并 r[fx] = (r[x]+1+r[y])%2;// //fx与x关系 + x与y的关系 + y与fy的关系 = fx与fy的关系 } } int main(void) { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); char op[2]; int x,y; init(); while(m--){ scanf("%s%d%d",op,&x,&y); if(op[0]=='A') { if(find(x)!=find(y)){//不在同一棵树里,所以不确定 printf("Not sure yet.\n"); continue; } if(re[x]==re[y]) printf("In the same gang.\n"); else printf("In different gangs.\n"); } else merge(x,y); } } return 0; }

转载请注明原文地址: https://www.6miu.com/read-1100184.html

最新回复(0)