并查集之字符串变种模板

class UnionFind:
    def __init__(self):
        self.parent = {}
 
    def find(self, a):
        if a not in self.parent:
            self.parent[a] = a
            return a
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a
 
    def merge(self, a, b):
        if a not in self.parent:
            self.parent[a] = a
        if b not in self.parent:
            self.parent[b] = b    
        self.parent[self.find(b)] = self.find(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21