2026 Spring 第七次上机

Python 判断等价关系是否成立.py 35 lines (30 loc) | 871 Bytes

Raw

1 n = int(input())
2 relations = [input() for _ in range(n)]
3 parent = [i for i in range(26)]  # 假设变量为26个小写字母，用0 - 25表示
4  
5 def find(x):
6     if parent[x] != x:
7         parent[x] = find(parent[x])
8     return parent[x]
9  
10 def union(x, y):
11     root_x = find(x)
12     root_y = find(y)
13     if root_x != root_y:
14         parent[root_x] = root_y
15  
16 # 处理等号关系
17 for relation in relations:
18     if relation[1] == '=':
19         x = ord(relation[0]) - ord('a')
20         y = ord(relation[3]) - ord('a')
21         union(x, y)
22  
23 # 处理不等号关系
24 for relation in relations:
25     if relation[1] == '!':
26         x = ord(relation[0]) - ord('a')
27         y = ord(relation[3]) - ord('a')
28         root_x = find(x)
29         root_y = find(y)
30         if root_x == root_y:
31             print('False')
32             break
33  
34 else:
35     print('True')

Python 宗教信仰.py 30 lines (26 loc) | 730 Bytes

Raw

1 def find(parent, x):
2     if parent[x] != x:
3         parent[x] = find(parent, parent[x])
4     return parent[x]
5  
6  
7 def union(parent, a, b):
8     a_root = find(parent, a)
9     b_root = find(parent, b)
10     if a_root < b_root:
11         parent[b_root] = a_root
12     else:
13         parent[a_root] = b_root
14  
15  
16 case_num = 1
17 while True:
18     n, m = map(int, input().split())
19     if n == 0 and m == 0:
20         break
21     parent = list(range(n + 1))
22     for _ in range(m):
23         i, j = map(int, input().split())
24         union(parent, i, j)
25     religion_count = 0
26     for i in range(1, n + 1):
27         if parent[i] == i:
28             religion_count += 1
29     print(f"Case {case_num}: {religion_count}")
30     case_num += 1

Python 食物链.py 40 lines (34 loc) | 960 Bytes

Raw

This code snippet is performing a series of operations on disjoint sets using the union-find algorithm. Here is a breakdown of the code: 1. The code reads two integers `n` and `k` from input and initializes a list called `parent` with values from 0 to `3 * n`. It also initializes a variable `false_count` to keep track of incorrect operations. 2. Two functions `find(x)` and `union(x, y)` are defined: - The `find(x)` function uses path compression to find the root of the set containing element `x`. - The `union(x, y)` function unions the sets containing elements `x` and `y` by updating their root nodes in the `parent` list. 3. A loop runs `k` times, parsing input values `d`, `x`, and `y`, adjusting `x` and `y` to be in the range `[0, n-1]`, and performing operations based on the value of `d`: - If `d` is 1, it checks conditions before performing unions and increments `false_count` if conditions are not met. - If `d` is 0, it again checks conditions before performing unions and increments `false_count` accordingly. 4. At the end of the loop, the code prints the final value of `false_count`. In summary, this code implements the union-find algorithm to handle different types of union operations on disjoint sets. The `false_count` variable keeps track of cases where the given operations are invalid. The code is designed to handle cases where elements are merged into different sets based on certain conditions.

1 n, k = map(int, input().split())
2 parent = list(range(3 * n))
3 false_count = 0
4  
5 def find(x):
6     if parent[x] != x:
7         parent[x] = find(parent[x])
8     return parent[x]
9  
10  
11 def union(x, y):
12     root_x = find(x)
13     root_y = find(y)
14     if root_x != root_y:
15         parent[root_y] = root_x
16  
17  
18 for _ in range(k):
19     d, x, y = map(int, input().split())
20     x -= 1
21     y -= 1
22     if x < 0 or x >= n or y < 0 or y >= n:
23         false_count += 1
24         continue
25     if d == 1:
26         if find(x) == find(y + n) or find(x) == find(y + 2 * n):
27             false_count += 1
28         else:
29             union(x, y)
30             union(x + n, y + n)
31             union(x + 2 * n, y + 2 * n)
32     else:
33         if x == y or find(x) == find(y) or find(x) == find(y + 2 * n):
34             false_count += 1
35         else:
36             union(x, y + n)
37             union(x + n, y + 2 * n)
38             union(x + 2 * n, y)
39  
40 print(false_count)

1	n = int(input())
2	relations = [input() for _ in range(n)]
3	parent = [i for i in range(26)] # 假设变量为26个小写字母，用0 - 25表示
4
5	def find(x):
6	if parent[x] != x:
7	parent[x] = find(parent[x])
8	return parent[x]
9
10	def union(x, y):
11	root_x = find(x)
12	root_y = find(y)
13	if root_x != root_y:
14	parent[root_x] = root_y
15
16	# 处理等号关系
17	for relation in relations:
18	if relation[1] == '=':
19	x = ord(relation[0]) - ord('a')
20	y = ord(relation[3]) - ord('a')
21	union(x, y)
22
23	# 处理不等号关系
24	for relation in relations:
25	if relation[1] == '!':
26	x = ord(relation[0]) - ord('a')
27	y = ord(relation[3]) - ord('a')
28	root_x = find(x)
29	root_y = find(y)
30	if root_x == root_y:
31	print('False')
32	break
33
34	else:
35	print('True')

1	def find(parent, x):
2	if parent[x] != x:
3	parent[x] = find(parent, parent[x])
4	return parent[x]
5
6
7	def union(parent, a, b):
8	a_root = find(parent, a)
9	b_root = find(parent, b)
10	if a_root < b_root:
11	parent[b_root] = a_root
12	else:
13	parent[a_root] = b_root
14
15
16	case_num = 1
17	while True:
18	n, m = map(int, input().split())
19	if n == 0 and m == 0:
20	break
21	parent = list(range(n + 1))
22	for _ in range(m):
23	i, j = map(int, input().split())
24	union(parent, i, j)
25	religion_count = 0
26	for i in range(1, n + 1):
27	if parent[i] == i:
28	religion_count += 1
29	print(f"Case {case_num}: {religion_count}")
30	case_num += 1

1	n, k = map(int, input().split())
2	parent = list(range(3 * n))
3	false_count = 0
4
5	def find(x):
6	if parent[x] != x:
7	parent[x] = find(parent[x])
8	return parent[x]
9
10
11	def union(x, y):
12	root_x = find(x)
13	root_y = find(y)
14	if root_x != root_y:
15	parent[root_y] = root_x
16
17
18	for _ in range(k):
19	d, x, y = map(int, input().split())
20	x -= 1
21	y -= 1
22	if x < 0 or x >= n or y < 0 or y >= n:
23	false_count += 1
24	continue
25	if d == 1:
26	if find(x) == find(y + n) or find(x) == find(y + 2 * n):
27	false_count += 1
28	else:
29	union(x, y)
30	union(x + n, y + n)
31	union(x + 2 * n, y + 2 * n)
32	else:
33	if x == y or find(x) == find(y) or find(x) == find(y + 2 * n):
34	false_count += 1
35	else:
36	union(x, y + n)
37	union(x + n, y + 2 * n)
38	union(x + 2 * n, y)
39
40	print(false_count)