luogu并查集

作者

P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最开始没用并查集，用207. 课程表的思路：

  1. n, k = map(int, input().split(" "))
  2. res = 0
  3. dic1 = collections.defaultdict(list)
  4. dic2 = collections.defaultdict(int)
  5. for i in range(k):
  6.     x, y, z = map(int, input().split(" "))
  7.     if y > n or z > n:
  8.         res += 1
  9.         continue
  10.     if x == 1:
  11.         dic2[y] = z
  12.         dic2[z] = y
  13.     elif x == 2:
  14.         if dic2[y] == z or dic2[z] == y or y == z:
  15.             res += 1
  16.         elif y in dic1[z]:
  17.             res += 1
  18.         else:
  19.             dic1[y].append(z)
  20. print(res)

结果只对了两个点

并查集做法：

  1. import collections
  2. import sys
  3. # 读取输入
  4. input = sys.stdin.readline
  5. n, k = map(int, input().split())
  6. # 并查集的初始化
  7. parent = list(range(3 * n + 1))
  9. def find(x):
  10.     if parent[x] != x:
  11.         parent[x] = find(parent[x])  # 路径压缩
  12.     return parent[x]
  14. def union(x, y):
  15.     root_x = find(x)
  16.     root_y = find(y)
  17.     if root_x != root_y:
  18.         parent[root_x] = root_y #找
  20. res = 0
  21. for _ in range(k):
  22.     x, y, z = map(int, input().split())
  23.     if y > n or z > n:
  24.         res += 1
  25.         continue
  27.     if x == 1:  # 1 X Y 表示 X 和 Y 是同类
  28.         if find(y) == find(z + n) or find(y) == find(z + 2 * n):
  29.             res += 1
  30.         else:
  31.             union(y, z)
  32.             union(y + n, z + n)
  33.             union(y + 2 * n, z + 2 * n)
  34.     elif x == 2:  # 2 X Y 表示 X 吃 Y
  35.         if find(y) == find(z) or find(y) == find(z + 2 * n):
  36.             res += 1
  37.         else:
  38.             union(y, z + n)
  39.             union(y + n, z + 2 * n)
  40.             union(y + 2 * n, z)
  41. print(res)

 这两天再研究下

发表评论