当前位置: 代码迷 >> 综合 >> POJ1703 Find them, Catch them(并查集)
  详细解决方案

POJ1703 Find them, Catch them(并查集)

热度:4   发布时间:2024-01-16 13:50:11.0

题意:

两个两个输入一些数,D代表这两个数不同,A代表查询这两个数是否相同

要点:

与食物链那一题类似,都是开多倍数组,储存每种情况


15321734 Seasonal 1703 Accepted 1680K 375MS C++ 973B 2016-03-27 18:34:06
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 100050
int p[maxn * 2], rank[maxn * 2];
int m, n;void init()
{for (int i = 1; i <= 2*m; ++i)//注意这里初始化要2*m{p[i] = i;rank[i] = 0;}
}
int find(int x)
{if (p[x] == x) return x;return p[x] = find(p[x]);
}
void merge(int x, int y)
{x = find(x);y = find(y);if (x == y) return;if (rank[x] > rank[y])p[y] = x;else{p[x] = y;if (rank[x] == rank[y]) ++rank[y];}
}
bool same(int x, int y)
{return find(x) == find(y);
}
int main()
{int t,i,x,y;char str;scanf("%d", &t);while (t--){scanf("%d%d", &m, &n);getchar();init();while(n--){scanf("%c%d%d", &str,&x,&y);getchar();			//这一步比较重要,清除缓冲区if (str == 'A'){if (same(x, y))printf("In the same gang.\n");else if (same(x, y + m))printf("In different gangs.\n");elseprintf("Not sure yet.\n");}else{merge(x, y + m);//合并X为A,Y为B的情况merge(x + m, y);//合并X为B,Y为A的情况}}}return 0;
}


  相关解决方案