Bob, a teacher of St. Joseph School given a task by his principal to merge the details of the students where each element details[i] is a list of strings, where the first element details[i][0] is a name of the student, and the rest of the elements are emails representing emails of the student.   Two details definitely belong to the same student if there is some common email to both detail.  After merging the details, return the details of the student in the following format: the first element of each detail is the name of the student, and the rest of the elements are emails in sorted order.  
Note: Two details have the same name, they may belong to different people as people could have the same name. A person can have any number of details initially, but all of their details definitely have the same name.
In case 2 or more same email belongs to 2 or more different names merge with first name only. Return the 2D list in the order in a sorted way according to the name of the details.
Example 1:
Input: 
n: 4
details = 
[["John","johnsmith@mail.com","john_newyork@mail.com"],
["John","johnsmith@mail.com","john00@mail.com"],
["Mary","mary@mail.com"],
["John","johnnybravo@mail.com"]]
Output: 
[["John","john00@mail.com","john_newyork@mail.com",
"johnsmith@mail.com"],["Mary","mary@mail.com"],
["John","johnnybravo@mail.com"]]
Explanation:
The first and second John's are the same person as 
they have the common email "johnsmith@mail.com".
The third 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.
Example 2:
Input: 
n: 5
details = 
[["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]]
Output: 
[["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]
Explanation:
We don't have any common emails in any of the users.
We just sorted the emails of each person and we
return a list of the emails.(The details can be
returned in any order).
Your Task:
You don't need to read or print anything. Your task is to complete the function mergeDetails() which takes 2D List of string details denoting the details of the students and returns the list of strings denoting the details of student after merging.
Expected Time Complexity: O(N*M*logN) - where N is the size of details length and M is the size of number of strings for a name.
Expected Auxiliary Space: O(N*M) - where N is the size of details length and M is the size of number of strings for a name.
Constraints:
	1 <= details.length <= 1000
	2 <= details[i].length <= 10
	1 <= details[i][j].length <= 30
	details[i][0] consists of English letters.
	details[i][j] (for j > 0) is a valid email.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Spanning trees

Starter code: #User function Template for python3





class Solution:

    def mergeDetails(self, details : List[List[str]]) -> List[List[str]]:

        # code here

Solutions:
class DisjointSet:

	def __init__(self, n):
		self.rank = [0 for i in range(n + 1)]
		self.parent = [i for i in range(n + 1)]
		self.size = [1 for i in range(n + 1)]

	def findUParent(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUParent(self.parent[node])
		return self.parent[node]

	def unionByRank(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.rank[up_u] < self.rank[up_v]:
			self.parent[up_u] = up_v
		elif self.rank[up_v] < self.rank[up_u]:
			self.parent[up_v] = up_u
		else:
			self.parent[up_v] = up_u
			self.rank[up_u] += 1
		return

	def unionBySize(self, u, v):
		up_u = self.findUParent(u)
		up_v = self.findUParent(v)
		if up_u == up_v:
			return
		if self.size[up_u] < self.size[up_v]:
			self.parent[up_u] = up_v
			self.size[up_v] += self.size[up_u]
		else:
			self.parent[up_v] = up_u
			self.size[up_u] += self.size[up_v]
		return
from collections import defaultdict

class Solution:

	def mergeDetails(self, details):
		n = len(details)
		ds = DisjointSet(n)
		mapping = defaultdict()
		name = defaultdict()
		for i in range(n):
			name[i] = details[i][0]
		for i in range(n):
			for j in range(1, len(details[i])):
				mail = details[i][j]
				if mail not in mapping:
					mapping[mail] = i
				else:
					ds.unionByRank(mapping[mail], i)
		ans = defaultdict(list)
		for mail in mapping:
			node = ds.parent[mapping[mail]]
			ans[node].append(mail)
		res = []
		for i in range(n):
			if len(ans[i]) == 0:
				continue
			ans[i].sort()
			temp = []
			temp.append(details[i][0])
			for it in ans[i]:
				temp.append(it)
			res.append(temp)
		res.sort()
		return res