实战 - Head of gang - 并查集

• 输入一串序列：Name1 Name2 Time表示A和B的通话时间，假定存在通话的人所在圈子大于2个人，认为是一个黑帮，在这个黑帮中，打电话时间最长的是老大
• 思路：使用并查集的思想构建节点的边关系，同时需要保存每个节点的通话时间
• 注意：①因为在初始化节点、边关系时，所有节点的总通话时间还不确定，所以不能过早确定边关系，等时间确定后，再确定边关系；②我的小弟的小弟还是我的小弟，所以在计算黑帮人数时，不能只计算和boss直接相关的，间接相关的也要计算上。

def headOfGang():
    MAX_ = 27
    father_ = [i for i in range(MAX_)]
    name_ = [None for i in range(MAX_)]
    visit_ = [False for i in range(MAX_)]
    time_ = [0 for i in range(MAX_)]
    height_ = [1 for i in range(MAX_)]

    def Initial():
        for i in range(MAX_):
            father_[i] = i
            name_[i] = None
            visit_[i] = False
            time_[i] = 0
            height_[i] = 1

    def Find(x):
        if x != father_[x]:
            father_[x] = Find(father_[x])
        return father_[x]

    def Union(x, y):
        x, y = Find(x), Find(y)
        if x != y:
            # x的通话时间比y长 -> x是上级
            if time_[x] > time_[y]:
                father_[y] = x
                height_[x] += height_[y] # 把y和他的小弟一起带上
            # y的通话时间比x长 -> y是上级
            elif time_[x] < time_[y]:
                father_[x] = y
                height_[y] += height_[x] # 把x和他的小弟一起带上
            else:
                father_[x] = y
                height_[y] += height_[x]

    while True:
        try:
            # n, k分别为电话数和通话时间阈值
            n, k = [int(i) for i in input().split()]
            x_list, y_list = [], []
            for i in range(n):
                x, y, time = input().split()
                x_index, y_index = ord(x[0]) - ord('A'), ord(y[0]) - ord('A')
                time = int(time)
                name_[x_index], name_[y_index] = x, y
                visit_[x_index], visit_[y_index] = True, True
                time_[x_index] += time
                time_[y_index] += time
                x_list.append(x_index)
                y_list.append(y_index)
            for x, y in zip(x_list, y_list):
                Union(x, y)
            gangHead = []
            for i in range(MAX_):
                if not visit_[i]:
                    continue
                if i == father_[i] and height_[i] > 2 and time_[i] > k:
                    gangHead.append(i)
            gangHead.sort()
            if len(gangHead):
                print(len(gangHead))
                for i in gangHead:
                    print('{} {}'.format(name_[i], height_[i]))
            else:
                print(0)
            Initial()
        except (EOFError, KeyboardInterrupt):
            break


if __name__ == '__main__':
    headOfGang()