# [Union-Find]
# https://leetcode.com/problems/accounts-merge/
# 721. Accounts Merge

# History:
# Facebook
# 1.
# Mar 28, 2020
# 2.
# Apr 28, 2020

# Given a list accounts, each element accounts[i] is a list of strings, where the first element
# accounts[i][0] is a name, and the rest of the elements are emails representing emails of the
# account.
#
# Now, we would like to merge these accounts. Two accounts definitely belong to the same person
# if there is some email that is common to both accounts. Note that even if two accounts have the
# same name, they may belong to different people as people could have the same name. A person can
# have any number of accounts initially, but all of their accounts definitely have the same name.
#
# After merging the accounts, return the accounts in the following format: the first element of
# each account is the name, and the rest of the elements are emails in sorted order. The accounts
# themselves can be returned in any order.
#
# Example 1:
# Input:
# accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John",
# "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary",
# "mary@mail.com"]]
# Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],  ["John",
# "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]]
# Explanation:
# The first and third John's are the same person as they have the common email "johnsmith@mail.com".
# The second John and Mary are different people as none of their email addresses are used by
# other accounts.
# We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'],
# ['John', 'johnnybravo@mail.com'],
# ['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be
# accepted.
# Note:
#
# The length of accounts will be in the range [1, 1000].
# The length of accounts[i] will be in the range [1, 10].
# The length of accounts[i][j] will be in the range [1, 30].


from collections import defaultdict


class UnionFindsetRank(object):
    def __init__(self):
        self.parents = {}
        self.rank = defaultdict(int)

    def union(self, i, j):
        i_root = self.find_root(i)
        j_root = self.find_root(j)

        if i_root == j_root:
            return

        if self.rank[i_root] > self.rank[j_root]:
            self.parents[j_root] = i_root
        elif self.rank[i_root] < self.rank[j_root]:
            self.parents[i_root] = j_root
        else:
            self.parents[j_root] = i_root
            self.rank[i_root] += 1

    def find_root(self, i):
        if i not in self.parents:
            self.parents[i] = i
        else:
            if i != self.parents[i]:
                self.parents[i] = self.find_root(self.parents[i])

        return self.parents[i]


class Solution(object):
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        union_find = UnionFindset()
        mp = {}

        for idx, account in enumerate(accounts):
            for i in range(1, len(account)):
                if account[i] not in mp:
                    mp[account[i]] = idx
                else:
                    union_find.union(idx, mp[account[i]])

        ret = defaultdict(set)

        for i in range(len(accounts)):
            root = union_find.find_root(i)
            ret[root] |= set(accounts[i][1:])

        return [
            [accounts[root_idx][0]] + sorted(list(emails))
            for root_idx, emails in ret.iteritems()
        ]


from collections import defaultdict


class UnionFind(object):
    def __init__(self):
        self.parents = {}

    def union(self, i, j):
        i_root = self.find_root(i)
        j_root = self.find_root(j)

        if i_root != j_root:
            self.parents[i_root] = j_root

    def find_root(self, i):
        if i not in self.parents:
            self.parents[i] = i
        else:
            if self.parents[i] != i:
                self.parents[i] = self.find_root(self.parents[i])

        return self.parents[i]


class SolutionUnionEmails(object):
    def accountsMerge(self, accounts):
        """
        :type accounts: List[List[str]]
        :rtype: List[List[str]]
        """
        union_find = UnionFind()
        for account in accounts:
            for i in range(2, len(account)):
                union_find.union(account[i], account[1])

        group = defaultdict(set)

        for account in accounts:
            for i in range(1, len(account)):
                root = union_find.find_root(account[i])
                group[(root, account[0])].add(account[i])

        ret = []
        for root, emails in group.iteritems():
            emails = sorted(list(emails))
            emails.insert(0, root[1])
            ret.append(emails)

        return ret
