#思想是搜索每一行的每一个邮箱，如果发现某一行的某个邮箱在之前行出现过，那么把该行的下标和之前行通过并查集来合并，
class Solution(object):
    def find(self, x):
        if x == self.parents[x]:
            return x
        else:
            return self.find(self.parents[x])
    def union(self,i, j):
        self.parents[self.find(i)] = self.find(j)
    def accountsMerge(self, accounts):
        # 用parents维护每一行的父亲节点
        # 如果parents[i] == i, 表示当前节点为根节点
        self.parents = [i for i in range(len(accounts))]
        print('==self.parents:', self.parents)
        dict_ = {}

        # 如果发现某一行的某个邮箱在之前行出现过，那么把该行的index和之前行合并（union）即可
        for i in range(len(accounts)):
            for email in accounts[i][1:]:
                if email in dict_:
                    self.union(dict_[email], i)
                else:
                    dict_[email] = i
        print('===self.parents:', self.parents)
        print('=== dict_:', dict_)
        import collections
        users = collections.defaultdict(set)
        print('==users:', users)
        res = []
        # 1. users：表示每个并查集根节点的行有哪些邮箱
        # 2. 使用set：避免重复元素
        # 3. 使用defaultdict(set)：不用对每个没有出现过的根节点在字典里面做初始化
        for i in range(len(accounts)):
            for account in accounts[i][1:]:
                users[self.find(i)].add(account)
        print('==users:', users)
        # 输出结果的时候注意结果需按照字母顺序排序（虽然题目好像没有说）
        for key, val in users.items():
            res.append([accounts[key][0]] + sorted(list(val)))

        return res


accounts = [["John", "johnsmith@mail.com", "john00@mail.com"],
            ["John", "johnnybravo@mail.com"],
            ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
            ["Mary", "mary@mail.com"]]

# [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
#  ["John", "johnnybravo@mail.com"],
#  ["Mary", "mary@mail.com"]]

sol = Solution()
res= sol.accountsMerge(accounts)
print(res)

228.连接所有点的最小费用

思路1: 其实就是求最小生成树，首先想到的是kruskal 但是时间复杂度较高,超时

# 其实就是求最小生成树:采用kruskal 但是时间复杂度较高,超时
class Solution:
    def minCostConnectPoints(self, points):
        edge_list = []
        nodes = len(points)
        for i in range(nodes):
            for j in range(i):
                dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edge_list.append([i, j, dis])
        print('==edge_list:', edge_list)
        edge_list = sorted(edge_list, key=lambda x: x[-1])
        print('==edge_list:', edge_list)
        group = [[i] for i in range(nodes)]
        print('==group:', group)
        res = 0
        for edge in edge_list:
            for i in range(len(group)):
                if edge[0] in group[i]:
                    m = i  # 开始节点
                if edge[1] in group[i]:
                    n = i  # 结束节点
            if m != n:
                # res.append(edge)
                res += edge[-1]
                group[m] = group[m] + group[n]
                group[n] = []
            print(group)
        print('==res:', res)
        return res

points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
sol = Solution()
sol.minCostConnectPoints(points)

# prim算法 超出时间限制
class Solution:
    def minCostConnectPoints(self, points):
        # edge_list = []
        nodes = len(points)
        Matrix = [[0 for i in range(nodes)] for j in range(nodes)]
        for i in range(nodes):
            for j in range(nodes):
                dis = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                # edge_list.append([i, j, dis])
                Matrix[i][j] = dis
        # print('===edge_list:', edge_list)
        print('==Matrix:', Matrix)
        selected_node = [0]
        candidate_node = [i for i in range(1, nodes)]  # 候选节点
        print('==candidate_node:', candidate_node)
        # res = []
        res = 0
        while len(candidate_node):
            begin, end, minweight = 0, 0, float('inf')
            for i in selected_node:
                for j in candidate_node:
                    if Matrix[i][j] < minweight:
                        minweight = Matrix[i][j]
                        begin = i  # 存储开始节点
                        end = j  # 存储终止节点
            # res.append([begin, end, minweight])
            print('==end:', end)
            res += minweight
            selected_node.append(end)  # 找到权重最小的边　加入可选节点
            candidate_node.remove(end)  # 候选节点被找到　进行移除
        print('==res:', res)
        return res


points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
# points = [[-1000000, -1000000], [1000000, 1000000]]
sol = Solution()
sol.minCostConnectPoints(points)