种类并查集

2020-03-07

字数统计: 305字 | 阅读时长≈ 1分钟

种类并查集的总结

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

1	#include <algorithm>
2	#include <iostream>
3	#include <cstring>
4	#include <cstdio>
5	using namespace std;
6	int pre[300000];
7	int fin(int a)
8	{
9	if (pre[a]==a) return a;
10	int t=a;
11	while (pre[a]!=a)
12	{
13	a=pre[a];
14	}
15	while (pre[t]!=t)
16	{
17	int t2=t;
18	t=pre[t];
19	pre[t2]=a;
20	}
21	return a;
22	}
23	int sam(int x, int y)
24	{
25	return fin(x) == fin(y);
26	}
27	void join(int x, int y)
28	{
29	int a = fin(x), b = fin(y);
30	if(a != b)pre[a] = b;
31	}
32	int main()
33	{
34	std::ios::sync_with_stdio(0);
35	int n, m, i, sum = 0, a1, a2;
36	scanf("%d", &sum);
37	while(sum--)
38	{
39	scanf("%d %d", &n, &m);
40	char cmd[15];
41	for(i = 1; i <= 2 * n; i++)pre[i] = i;
42	for(i = 1; i <= m; i++)
43	{
44	getchar();
45	scanf("%s %d %d", &cmd, &a1, &a2);
46	if(strcmp(cmd, "A") == 0)
47	{
48	if(sam(a1, a2 + n) \|\| sam(a2, a1 + n))printf("In different gangs.\n");
49	else if(sam(a1, a2) \|\| sam(a1 + n, a2 + n))
50	{
51	join(a1, a2);
52	join(a1 + n, a2 + n);
53	printf("In the same gang.\n");
54	}
55	else printf("Not sure yet.\n");
56	}
57	else
58	{
59	join(a1,a2 + n);
60	join(a2, a1 + n);
61	}
62	}
63	}
64	return 0;
65	}