poj 1703 Find them, Catch them 并查集

缘起

日常浪费生命 poj 1703 Find them, Catch them

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
有n个人分别属于两个团伙，接下来m组形如 ch, x, y的数据，ch为“D"表示 x, y属于不同的团伙，ch为"A"表示
询问x，y是否属于同一个团伙；

【输入】
多样例，第一行的数字T就是样例数. 每个样例先是两个整数N(N <= 10^5)和M（M <= 10^5），然后是M行，要么是
D x y 表示 x和y属于不同的团伙
要么是
A x y 询问x和y是否属于同一个团伙

【输出】
对于询问A，要根据之前的信息判断x和y是否属于同一个团伙，输出见样例

【样例输入】
1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

【样例输出】
Not sure yet.
In different gangs.
In the same gang.

【限制】
1s

【来源】
poj月赛

浓浓的并查集味道~ 其实这属于”种类不明”的并查集问题. 这个和之前一道”食物链”的题目很像——都是”种类不明”的并查集问题（见【1】）. 解决方法可以借鉴【1】中的. 对于

D x y 这种询问, 只需要merge (x,A)(y,B) 和 (x,B)(y,A) 就行了. A,B分别表示两个团伙. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL

int f[200005],n,m; // 因为每个元素都会扩展出2个, 例如i,(i,A)表示i属于A团伙,和(i,B)表示i属于B团伙, 将形如(i,B)的数据放在后半段

int getf(int i)
{
	return f[i]<0?i:f[i]=getf(f[i]);
}

void merge(int i, int j)
{
	int fi = getf(i), fj = getf(j);
	if (fi==fj)
	{
		return;
	}
	if (f[fi]<f[fj])
	{
		f[fi]+=f[fj];
		f[fj]=fi;
	}
	else
	{
		f[fj]+=f[fi];
		f[fi] = fj;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		memset(f, -1, sizeof(f));
		scanf("%d%d", &n, &m);
		getchar();
		while(m--)
		{
			char a;
			int x,y;
			a=  getchar();
			scanf("%d%d", &x, &y);
			getchar();
			if (a=='D') // x和y不属于一个团伙, 则merge(x,y+n)和merge(x+n,y)
			{
				merge(x,y+n); // 插入 (x,A)和 (y,B)以及 (x,B)和(y,A)
				merge(x+n,y);
			}
			else
			{
				if (getf(x)==getf(y) && getf(x+n)==getf(y+n)) // 如果x和y同属于A团伙或者B团伙
				{
					puts("In the same gang.");
				}
				else if (getf(x)==getf(y+n) && getf(x+n)==getf(y)) // 如果不属于同一个团伙
				{
					puts("In different gangs.");
				}
				else
				{
					puts("Not sure yet.");
				}
			}
		}
	}
	return 0;
}

ac情况 （1A什么的，最爽了~）

Status Accepted
Time 360ms
Memory 864kB
Length 1175
Lang C++
Submitted 2019-08-30 10:43:24
Shared
RemoteRunId 20818160

参考

【1】https://yfsyfs.github.io/2019/08/21/poj-1182-%E9%A3%9F%E7%89%A9%E9%93%BE-%E5%B8%A6%E6%9D%83%E5%B9%B6%E6%9F%A5%E9%9B%86%E6%A8%A1%E6%9D%BF%E9%A2%98/