数据结构（六）UnionFind

之前面试蘑菇街GG了，竟然是因为不懂UnionFind，来总结一下下啦。

def UnionFind(m, L):
    temp = [i for i in range(m)]
    for a, b in L:
        if temp[a-1] == temp[b-1]:
            continue
        temp_a, temp_b = temp[a-1], temp[b-1]  #这里是个坑，一定要这么写
        for i in range(len(temp)):
            if temp[i] == temp_b:
                temp[i] = temp_a
    return len(set(temp))

用BFS也是可以的啦～

import collections
def UnionFind2(m, L):
    mydic = collections.defaultdict(list)
    for a,b in L:
        mydic[a].append(b)
        mydic[b].append(a)
    res = 0
    visited = [0 for _ in range(m)]
    for i in range(1,m+1):
        if i in mydic and not visited[i-1]:
            res += 1
            BFS(mydic, visited, i)
            print(i,res,visited)
    return res + m - sum(visited)
def BFS(mydic, visited, index):
    qu = [index]
    while qu:
        people = qu.pop(0)
        visited[people-1] = 1
        for f in mydic[people]:
            if not visited[f-1]:
                visited[people-1] = 1
                qu.append(f)