## Algorithm

Problem Name: 721. Accounts Merge

Given a list of `accounts` where 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 common email 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","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: accounts = [["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"]]
```

Constraints:

• `1 <= accounts.length <= 1000`
• `2 <= accounts[i].length <= 10`
• `1 <= accounts[i][j].length <= 30`
• `accounts[i][0]` consists of English letters.
• `accounts[i][j] (for j > 0)` is a valid email.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List> accountsMerge(List> accounts) {
for (List account : accounts) {
String firstEmail = account.get(1);
for (int i = 2; i < account.size(); i++) {
}
}
Set visited = new HashSet<>();
List> mergedAccounts = new ArrayList<>();
for (List account : accounts) {
String name = account.get(0);
String firstEmail = account.get(1);
if (!visited.contains(firstEmail)) {
Stack stack = new Stack<>();
stack.push(firstEmail);
List mergedAccount = new ArrayList<>();
while (!stack.isEmpty()) {
String removedEmail = stack.pop();
for (String neighbor : adjacencyList.getOrDefault(removedEmail, new ArrayList<>())) {
if (!visited.contains(neighbor)) {
stack.push(neighbor);
}
}
}
Collections.sort(mergedAccount.subList(1, mergedAccount.size()));
}
}
return mergedAccounts;
}
}
``````
Copy The Code &

Input

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

Output

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

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const accountsMerge = function (accounts) {
const roots = new Set()
const owner = {}
const parent = {}
const children = {}

for (let account of accounts) {
let [user, root, ...emails] = account
let r1 = find(root)
owner[root] = user
children[r1] = children[r1] || [root]

for (let email of emails) {
let r2 = find(email)
if (r2 !== r1) {
parent[r2] = r1
children[r1].push(...(children[r2] ? children[r2] : [email]))
roots.delete(r2)
delete children[r2]
}
}
}

return [...roots].map((r) => [owner[r], ...children[r].sort()])

function find(a) {
parent[a] = parent[a] || a
return a === parent[a] ? a : find(parent[a])
}
}
``````
Copy The Code &

Input

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

Output

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

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def accountsMerge(self, accounts):
def explore(mail, q):
q += mail,
for v in edges[mail]:
if v not in visited: explore(v, q)
return q
edges, owner, visited, res = collections.defaultdict(list), {}, set(), []
for acc in accounts:
owner[acc[1]] = acc[0]
for i in range(1, len(acc) - 1):
if acc[i] != acc[i + 1]:
edges[acc[i]] += acc[i + 1],
edges[acc[i + 1]] += acc[i],
for acc in accounts:
if acc[1] not in visited: res += [acc[0]] + sorted(explore(acc[1], [])),
return res
``````
Copy The Code &

Input

cmd
accounts = [["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"]]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0721_AccountsMerge
{
public IList> AccountsMerge(IList> accounts)
{
var uf = new UnionFind();
var emailToName = new Dictionary();
var emailToId = new Dictionary();

var id = 0;
foreach (var account in accounts)
{
var name = string.Empty;
foreach (var str in account)
{
if (name == string.Empty)
{
name = str;
continue;
}

emailToName[str] = name;
if (!emailToId.ContainsKey(str))
emailToId[str] = id++;
uf.Union(emailToId[account[1]], emailToId[str]);
}
}

var map = new Dictionary>();
foreach (var email in emailToName.Keys)
{
var index = uf.Find(emailToId[email]);
if (!map.ContainsKey(index))
map[index] = new List();
}

return map.Values.Select(list =>
{
IList temp = list.OrderBy(e => e, StringComparer.Ordinal).ToList();
temp.Insert(0, emailToName[list[0]]);
return temp;
}).ToList();
}

public class UnionFind
{
private int[] parents;

public UnionFind()
{
parents = new int[10001];
for (int i = 0; i < 10001; i++)
parents[i] = i;
}

public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);
return parents[index];
}

public void Union(int index1, int index2)
{
parents[Find(index1)] = Find(index2);
}
}
}
}
``````
Copy The Code &

Input

cmd
accounts = [["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

cmd
[["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"]]