并查集简单应用

发表于 | 更新于

食物链

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。

A吃B， B吃C，C吃A。

现有N个动物，以1－N编号。

每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是”1 X Y”，表示X和Y是同类。

第二种说法是”2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N和K句话，输出假话的总数。

输入格式

第一行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

若D=1，则表示X和Y是同类。

若D=2，则表示X吃Y。

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤50000,
0≤K≤100000

输入样例：

1
2
3
4
5
6
7
8
100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输出样例：

3

思想:

由于有a，b，c三种动物，$a -> b$, $b -> c$, $c -> a$，的这种关系，且题设也没告诉具体是哪种物种，所以三种情况全考虑
用0 ~ n - 1表示a，n ~ 2 n - 1表示b, 2 n ~ 3 * n - 1表示c 

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 <iostream>
#include <algorithm>
const int MN = 50005;
int par[MN * 3], heig[MN * 3];				//初始化3个 
int n, k;
void init(int n)			//并查集模板 
{
	for(int i = 0; i < n; i ++)			
		par[i] = i;
}

int find(int x)			
{
	if(par[x] == x)	return x;		
	return par[x] = find(par[x]);		
}

void unite(int x, int y)		
{
	x = find(x);			
	y = find(y);	
	if(x == y)	return;			
	if(heig[x] < heig[y])			
		par[x] = y;							
	else
	{
		par[y] = x;		  
		if(heig[x] == heig[y])	heig[x] ++;		
	}
}
bool same(int x, int y)				
{
	return find(x) == find(y);
}
using namespace std;
int main()
{
	cin >> n >> k;
	init(n * 3);
	int ans = 0;
	while(k --)
	{
		int opt, x, y;
		scanf("%d %d %d", &opt, &x, &y); 
		if(x <= 0 || x > n || y <= 0 || y > n)			//越界错误次数即答案+1 
		{
			ans ++;
			continue;
		}
		x -- , y --;		//由于下标从0开始，-- 对应 
		if(opt & 1)		//第一种操作 "查询是否为同一物种" 
		{
			if(same(x, y + n) || same(x, y + 2 * n))	//x，y肯定为同一物种，如果x 和y的其它两种状态任意一种在同一个集合中那么就矛盾，ans ++ 
				ans ++;
			else
			{
				unite(x, y);			//每个对应的合并，3种情况全部考虑 
				unite(x + n, y + n);
				unite(x + 2 * n, y + 2 * n);
			}
		}
		else
		{
			if(same(x, y) || same(x, y + 2 * n))		//如果吃同类或者出现a -> c ,b -> a, c -> b的情况就是错误的，即跨两个吃就是已经逆向循环了 
				ans++;
			else
			{
				unite(x, y + n);			//如果是正确的那么就建立起a -> b, b -> c, c -> a的情形 
				unite(x + n, y + 2 * n);
				unite(x + n * 2, y);
			}
		}
	}
	cout << ans;
	return 0;
}

网络维修

电话线公司（TLC）正在建立一个新的电话电缆网络。它们连接了几个由1到N的整数编号的位置。

没有两个地方有相同的号码。线路是双向的，并且总是将两个地方连接在一起，

并且每个地方线路终止于电话交换机。每个地方都有一个电话交换机。它来自每个地方

可以通过线路到达其他地方，但它不需要是直接连接，它可以通过几次间接连接。

有时电源在某个地方发生故障，因而交换机无法运行。 TLC的官员意识到，在这种情况下，

除了故障的地方无法到达的之外，这也可能导致其他地方无法相互连接。

在这种情况下，我们会说地点（故障的地方）是至关重要的。

现在，官员正试图编写一个程序来查找所有这些关键位置的数量。帮助他们。

输入

输入文件由几个行块组成。每个块描述一个网络。在每个块的第一行中，存在N <100的位数。

接下来最多N行中的每一行包含一个地点的编号，后面跟有来自该地方的直线的一些地方的编号。

这些最多N行完全描述了网络，即，网络中两个地方的每个直接连接至少包含在一行中。一行中的所有数字都是分开的

一个。每个块以一条仅包含0的行结束。最后一个块只有一行，N = 0;

输出

输出包含除输入文件中的最后一个块之外的每个块，其中一行包含关键位置的数量。

样例输入

1
2
3
4
5
6
7
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0

样例输出

1
2
1
2

提示

您需要确定一行的结尾。为了使其易于确定，在每行结束之前没有多余的空白。

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
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1005;
struct point{			//结构体坐标 (使用pair<>型也可)
	int x, y;
}a[N];
int n, d;
int par[N], rk[N], vis[N];			//父亲节点，高度，访问标记数组 

void init()					//初始化每个点一个集合，自己为自己的根节点 
{
	for(int i = 1; i <= n; i ++)
		par[i] = i;
}
int find(int x)		//寻找根节点 
{
	if(x == par[x])	return x;
	return par[x] = find(par[x]);
}

void unite(int x, int y)			//根据树的高度进行合并 
{
	x = find(x), y = find(y);
	if(x == y)	return ;
	if(rk[x] > rk[y])	par[y] = x;
	else
	{
		par[x] = y;
		if(rk[x] == rk[y])	rk[y] ++;
	}
}

bool same(int x, int y)					//判断是否为一个集合(即根节点是否相同) 
{
	return find(x) == find(y);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> d;
	init();
	for(int i = 1; i <= n ;i ++)
		cin >> a[i].x >> a[i].y;	
	int t = n + 2;
	char opt;
	while(cin >> opt)
	{
		int p;
		cin >> p;
		if(opt == 'O')	
		{
			vis[p] = 1;
			for(int i = 1; i <= n; i ++)
				if(vis[i])
				{
					int dis = (a[p].x - a[i].x)	* (a[p].x - a[i].x)	+ (a[p].y - a[i].y) *( a[p].y - a[i].y);	//哈密顿距离小于给定距离并且次点被
									//访问过(即修过)就可以进行合并 
					if(dis <= d * d)
						unite(p, i);
				}
		}
		else
		{
			int q;
			cin >> q;
			if(!vis[q] || !vis[p])	cout << "FAIL\n";			//如果其中有一个没有被访问过 
			else if(same(q, p))	cout << "SUCCESS\n";		//如果都访问过且根节点相同 
			else	cout << "FAIL\n";						//根基点不同 
		}
	}
	return 0;
}
0%