题目链接:poj 1703 Find them, Catch them
题目大意:在城市中有两个大的帮派,Gang Dragon 和Gang Snake,先在有n个人被抓了,警察队他们进行m次操作,操作分为两种,询问A a b, 要求判断a和b是不是属于同一个团伙,D a b 表示说a b不属于同一个团伙。
解题思路:带权并查集的简单版,权值为1表示和前一个人不属于同一个团伙,为0表示属于同一个团伙。
#include <stdio.h>
#include <string.h>
const int N = 1e5+5;
int n, m, f[N], v[N];
int getfar(int x) {
if (x != f[x]) {
int t = f[x];
f[x] = getfar(f[x]);
v[x] = (v[x] + v[t]) % 2;
}
return f[x];
}
void init () {
scanf("%d%d", &n, &m);
for (int i = 0; i <= n; i++)
f[i] = i;
memset(v, 0, sizeof(v));
}
int main () {
int cas, a, b;
char str[10];
scanf("%d", &cas);
while (cas--) {
init ();
for (int i = 0; i < m; i++) {
scanf("%s%d%d", str, &a, &b);
int p = getfar(a), q = getfar(b);
if (str[0] == 'A') {
if (p != q)
printf("Not sure yet.\n");
else if (v[a] == v[b])
printf("In the same gang.\n");
else
printf("In different gangs.\n");
} else {
if (p != q) {
f[q] = p;
v[q] = (v[a] + 1 - v[b])%2;
}
}
}
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
北大POJ3278-Catch That Cow 解题报告+AC代码
poj 食物链代码.带权并查集,关键是找到其中的一些关系式.
并查集基础 acm 算法 poj oi 并查集基础.ppt
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
poj 1611 The Suspects 代码 并查集的应用
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ1089 并查集可以解决 并查集加路径压缩
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
搜索......................................................