集合题解

P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

并查集模板

看两个数是不是在一个集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
n, m, p  = map(int, input().split())

fa = [i for i in range(100010)]

def find(x) -> int:
    if fa[x] == x:
        return x
    fa[x] = find(fa[x])
    return fa[x]

def union(x, y):
    fa[find(x)] = find(y)


for _ in range(m):
    a, b = map(int, input().split())
    union(a, b)
for _ in range(p):
    a, b = map(int, input().split())
    if find(a) == find(b):
        print("Yes")
    else:
        print("No")

Loading - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

不是看两个数是不是在一个集合 而是计算一共有多少个集合

计算还需要修几条路才能把所有村子连接起来 其实就是求现在的集合数 连起来的村子当同一个村子 当fa[i] == i 的时候 cnt + 1 因为每个集合有且仅有一个 fa[i] == i 因此可以用来计数 最后 村子数减一就是道路数

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
def find(x):
    if x == fa[x]:
        return x
    fa[x] = find(fa[x])
    return fa[x]

def union(x, y):
    fa[find(x)] = find(y)


while True:
    l = list(map(int, input().split()))
    n = l[0]
    if n == 0:
        break
    m = l[1]
    fa = [i for i in range(100010)]

    cnt = 0
    for _ in range(m):
        a, b = map(int, input().split())
        union(a, b)
    for i in range(1, n + 1):
        if fa[i] == i:
            cnt += 1

    print(cnt - 1)

P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

为每个字符串求一个hash值 直接放入列表中 排序列表 然后看相邻的两个数的值是否一样

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
base = 131
prime = 233317
mod = 212370440130137957

def hashe(s):
    ans = 0
    for char in s:
        ans = (ans * base + ord(char)) % mod + prime
    return ans

n = int(input())
a = []

for _ in range(n):
    s = input()
    a.append(hashe(s))

a.sort()
ans = 1

for i in range(n - 1):
    if a[i] != a[i + 1]:
        ans += 1

print(ans)

[P3405 USACO16DEC] Cities and States S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

求城市对数 算出每个城市的hash值（只需要看前两位） 如果AB不是同一座城市 那么A B就是一个城市对 先放入mp中存起来 而B A可以直接加到答案里（题目要求有两个城市互为对的时候才算一个 比如MIAMT FL 和 FLINT 和 MI 算一对）所以每次遇到A B都先存着 知道遇到B A再一次取出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
ans = 0
mp = [[0] * 676 for _ in range(676)]
for _ in range(n):
    a, b = input().split()
    A = (ord(a[0]) - ord('A')) * 26 + ord(a[1]) - ord('A')
    B = (ord(b[0]) - ord('A')) * 26 + ord(b[1]) - ord('A')

    if A != B:
        mp[A][B] += 1  
        ans += mp[B][A]


print(ans)

P1102 A-B 数对 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

计数 然后看mp中有没有A - k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n, k = map(int,input().split())
nums = list(map(int, input().split()))
mp = {}
for i, x in enumerate(nums):
    if x in mp:
        mp[x] += 1
    else:
        mp[x] = 1

ans = 0
for key, value in mp.items():
    if key - k in mp:
       ans += mp[key - k] * value

print(ans)

[P1525 NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

带权并查集 并且一共只有两个集合 判断每个集合里面要放哪些

首先定义fa数组和Enemy（空数组） 对所有囚犯的怒气值从大到小排序 把最大的分别放到不同的集合 直到出现冲突（比如有个人A 和B 前面有一个在1监狱已经放好 而且B被放到2监狱（因为1和B的仇恨更大）这个人没办法 只能被放到1 和B仇恨较小的那个监狱）由于排序了 这个值就是最大值 带权值的并查集 只要用结构体加上w就行

记住只有两个集合里面放的操作 如果Enemy[A] 为0 那就把Enemy[A]赋值为B 不为0则合并Enemy[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
import sys


class node:
    def __init__(self, fo,to,w):
        self.fo = fo
        self.to = to
        self.w = w


def find(k):
    if fa[k] == k:
        return k
    fa[k] = find(fa[k])
    return fa[k]


def union(x, y):
    fa[find(x)] = find(y)


n, m = map(int, input().split())
fa = [i for i in range(n + 1)]
Enemy = [0] * 100010
p = [node(0,0,0) for _ in range(100010)]
for i in range(1,m + 1):
    u, v, w = map(int, input().split())
    p[i].fo = u
    p[i].to = v
    p[i].w = w

p.sort(key=lambda x: -x.w)

for i in range(m):
    # 如果已经在同一监狱
    t1, t2 = find(p[i].fo), find(p[i].to)
    if t1 == t2:
        print(p[i].w)
        sys.exit()

    if Enemy[p[i].fo] == 0:
        Enemy[p[i].fo] = p[i].to
    else:
        union(Enemy[p[i].fo], p[i].to)

    if Enemy[p[i].to] == 0:
        Enemy[p[i].to] = p[i].fo
    else:
        union(Enemy[p[i].to], p[i].fo)

print(0)

P1621 集合 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

最终的集合数其实就是算素数的个数 因为非素数都会被合并 每次合并总集合都减去一

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
def find(x):
    if x == fa[x]:
        return x
    fa[x] = find(fa[x])
    return fa[x]

def union(x, y):
    fa[find(x)] = find(y)


a, b, p = map(int, input().split())
ans = b - a + 1
fa = [i for i in range(100010)]
prime = [0] * (b + 1)
prime[1] = 1
for i in range(2, b + 1):
    if prime[i] == 0:
        if i >= p:
            for j in range(i * 2, b + 1, i):
                prime[j] = True
                if j - i >= a and find(j) != find(j - i):
                    union(j, j - i)
                    ans -= 1
        else:
            for j in range(i * 2, b + 1, i):
                prime[j] = True


print(ans)

[P1892 BOI2003] 团伙 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

记住只有两个集合里面放的操作 如果Enemy[A] 为0 那就把Enemy[A]赋值为B 不为0则合并Enemy[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
def find(x):
    if x == fa[x]:
        return x
    fa[x] = find(fa[x])
    return fa[x]

def union(x, y):
    fa[find(x)] = find(y)

n = int(input())
m = int(input())
fa = [i for i in range(100010)]
Enemy = [0] * 100010
for _ in range(m):
    op, a, b = input().split()
    a = int(a)
    b = int(b)

    if op == 'E':
        if Enemy[a] == 0:
            Enemy[a] = find(b)
        else:
            union(Enemy[a], b)
        if Enemy[b] == 0:
            Enemy[b] = find(a)
        else:
            union(a, Enemy[b])
    if op == 'F':
        union(a,b)

count = [0] * 1001
for i in range(1, n + 1):
    count[find(i)] = 1

cnt= 0
for i in range(1, n + 1):
    cnt += count[i]

print(cnt)

765. 情侣牵手 - 力扣（LeetCode）

n对情侣要相邻 (0, 1)(2, 3)(4, 5)… 从 因此可以分组 01为第0组 23为第1组 45 为第2组… 恰好0 1 / 2 = 0 2 3 / 2 = 1 4 5 / 2 = 2 这样来分组

如果两组情侣坐错了 那只需要其中两个人互换一次就可以 三组情侣坐错 只需要互换两次就可以 即k对错误的情侣 需要k - 1次交换就可以

注意 三个互相坐错 2次 若是两组 3个互相坐错就是 4次…（称为一个环）

就寻找有几个相互坐错的环 每个环 求环的大小减1就行

用并查集来写 坐错的就加到一个集合里 最后统计每个集合要交换的个数相加

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
class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        def find(x):
            if x == fa[x]:
                return x
           	fa[x] = find(fa[x])
            return fa[x]
      	
        def union(x, y):
            fa[find(x)] = find(y)
        
        
        n = len(row)
        m = n // 2
        fa = [i for i in range(m)]
        for i in range(0, n, 2):
            """
            0 1 union(0, 0) 就是把0 合到 0 不变 下面去比的时候 0 == find(0) 就是集合0 
            若是0 3 union(0, 1) 即 集合1 合到集合1 那么find(1) = 0下面找 1 != find(1)那就不是
            """
            union(row[i] // 2, row[i + 1] // 2)
        
        cnt = 0
        for i in range(m):
            if find(i) == i:
                cnt += 1
        return m - cnt
algorithm
#Ans
集合题解
https://brtulien.github.io/2023/09/30/集合题解/
作者
Brtulien
发布于
2023年9月30日
更新于
2024年7月1日
许可协议