<p>Given a list of <code>accounts</code> where each element <code>accounts[i]</code> is a list of strings, where the first element <code>accounts[i][0]</code> is a name, and the rest of the elements are <strong>emails</strong> representing emails of the account.</p>

<p>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.</p>

<p>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 <strong>in sorted order</strong>. The accounts themselves can be returned in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> accounts = [[&quot;John&quot;,&quot;johnsmith@mail.com&quot;,&quot;john_newyork@mail.com&quot;],[&quot;John&quot;,&quot;johnsmith@mail.com&quot;,&quot;john00@mail.com&quot;],[&quot;Mary&quot;,&quot;mary@mail.com&quot;],[&quot;John&quot;,&quot;johnnybravo@mail.com&quot;]]
<strong>Output:</strong> [[&quot;John&quot;,&quot;john00@mail.com&quot;,&quot;john_newyork@mail.com&quot;,&quot;johnsmith@mail.com&quot;],[&quot;Mary&quot;,&quot;mary@mail.com&quot;],[&quot;John&quot;,&quot;johnnybravo@mail.com&quot;]]
<strong>Explanation:</strong>
The first and second John&#39;s are the same person as they have the common email &quot;johnsmith@mail.com&quot;.
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 [[&#39;Mary&#39;, &#39;mary@mail.com&#39;], [&#39;John&#39;, &#39;johnnybravo@mail.com&#39;], 
[&#39;John&#39;, &#39;john00@mail.com&#39;, &#39;john_newyork@mail.com&#39;, &#39;johnsmith@mail.com&#39;]] would still be accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> accounts = [[&quot;Gabe&quot;,&quot;Gabe0@m.co&quot;,&quot;Gabe3@m.co&quot;,&quot;Gabe1@m.co&quot;],[&quot;Kevin&quot;,&quot;Kevin3@m.co&quot;,&quot;Kevin5@m.co&quot;,&quot;Kevin0@m.co&quot;],[&quot;Ethan&quot;,&quot;Ethan5@m.co&quot;,&quot;Ethan4@m.co&quot;,&quot;Ethan0@m.co&quot;],[&quot;Hanzo&quot;,&quot;Hanzo3@m.co&quot;,&quot;Hanzo1@m.co&quot;,&quot;Hanzo0@m.co&quot;],[&quot;Fern&quot;,&quot;Fern5@m.co&quot;,&quot;Fern1@m.co&quot;,&quot;Fern0@m.co&quot;]]
<strong>Output:</strong> [[&quot;Ethan&quot;,&quot;Ethan0@m.co&quot;,&quot;Ethan4@m.co&quot;,&quot;Ethan5@m.co&quot;],[&quot;Gabe&quot;,&quot;Gabe0@m.co&quot;,&quot;Gabe1@m.co&quot;,&quot;Gabe3@m.co&quot;],[&quot;Hanzo&quot;,&quot;Hanzo0@m.co&quot;,&quot;Hanzo1@m.co&quot;,&quot;Hanzo3@m.co&quot;],[&quot;Kevin&quot;,&quot;Kevin0@m.co&quot;,&quot;Kevin3@m.co&quot;,&quot;Kevin5@m.co&quot;],[&quot;Fern&quot;,&quot;Fern0@m.co&quot;,&quot;Fern1@m.co&quot;,&quot;Fern5@m.co&quot;]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= accounts.length &lt;= 1000</code></li>
	<li><code>2 &lt;= accounts[i].length &lt;= 10</code></li>
	<li><code>1 &lt;= accounts[i][j].length &lt;= 30</code></li>
	<li><code>accounts[i][0]</code> consists of English letters.</li>
	<li><code>accounts[i][j] (for j &gt; 0)</code> is a valid email.</li>
</ul>

// 下面这种方法是使用 BFS 来解的，建立了每个邮箱和其所有出现的账户数组之间的映射，比如还是这个例子：

// ["John", "a@gmail.com", "b@gmail.com"]

// ["John", "c@gmail.com", "d@gmail.com"]

// ["John", "a@gmail.com", "c@gmail.com"]

// 那么建立的映射就是：

// "a@gmail.com" -> [0, 2]

// "b@gmail.com" -> [0]

// "c@gmail.com" -> [1, 2]

// "d@gmail.com" -> [1]

// 然后还需要一个 visited 数组，来标记某个账户是否已经被遍历过，0表示为未访问，1表示已访问。在建立好 HashMap 之后，遍历所有的账户，如果账户未被访问过，将其加入队列 queue，新建一个 TreeSet，此时进行队列不为空的 while 循环，取出队首账户，将该该账户标记已访问1，此时将该账户的所有邮箱取出来放入数组 mails 中，然后遍历 mails 中的每一个邮箱，将遍历到的邮箱加入 TreeSet 中，根据映射来找到该邮箱所属的所有账户，如果该账户未访问，则加入队列中并标记已访问。当 while 循环结束后，当前账户的所有合并后的邮箱都保存在 TreeSet 中，将其转为字符串数组，并且加上用户名在首位置，最后加入结果 res 中即可

// Time complexity: O(NKlogNK)

// In the worst case, all the emails will end up belonging to a single person. The total number of emails will be N*KN∗K, and we need to sort these emails. DFS traversal will take NKNK operations as no email will be traversed more than once.

// Space complexity: O(NK)

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, vector<string>> graph; // To store the adjacency list of the graph
        unordered_map<string, string> emailToName;   // To map each email to the corresponding account name

        // Build the graph and the emailToName map
        for (auto& account : accounts) {
            string name = account[0];  // The first element is the account name
            for (int i = 1; i < account.size(); ++i) {
                emailToName[account[i]] = name;  // Map each email to the account name
                if (i == 1) continue;  // Skip the first email in the account as it has no previous email to connect
                // Add an undirected edge between the current email and the previous email
                graph[account[i]].push_back(account[i - 1]);
                graph[account[i - 1]].push_back(account[i]);
            }
        }

        unordered_set<string> visited;  // To keep track of visited emails
        vector<vector<string>> result;  // To store the final merged account lists

        // Perform BFS to find all connected components (i.e., all emails that belong to the same person)
        for (auto& [email, name] : emailToName) {
            if (visited.count(email)) continue;  // Skip already visited emails

            queue<string> q;
            q.push(email);
            visited.insert(email);
            vector<string> component;  // To store all emails in the current connected component

            // BFS to explore all emails connected to the current email
            while (!q.empty()) {
                string node = q.front();
                q.pop();
                component.push_back(node);  // Add the email to the current component
                for (const string& neighbor : graph[node]) {  // Explore all connected emails
                    if (!visited.count(neighbor)) {
                        visited.insert(neighbor);
                        q.push(neighbor);  // Add unvisited connected emails to the queue
                    }
                }
            }

            sort(component.begin(), component.end());  // Sort the emails lexicographically
            component.insert(component.begin(), name); // Insert the account name at the beginning of the component
            result.push_back(component);  // Add the sorted component to the result
        }

        return result;  // Return the final merged accounts
    }
};


// The key task here is to connect those emails
// to group these emails, each group need to have a representative, or parent.
// At the beginning, set each email as its own representative.
// Emails in each account naturally belong to a same group, and should be joined by assigning to the same parent (let's use the parent of first email in that list);
// Simple Example:

// a b c // now b, c have parent a
// d e f // now e, f have parent d
// g a d // now abc, def all merged to group g

// parents populated after parsing 1st account: a b c
// a->a
// b->a
// c->a

// parents populated after parsing 2nd account: d e f
// d->d
// e->d
// f->d

// parents populated after parsing 3rd account: g a d
// g->g
// b->g
// d->g

// class Solution {
// public:
//     vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
//         vector<vector<string>> res;
//         unordered_map<string, string> root; // email->root email
//         unordered_map<string, string> owner; // email->person
//         unordered_map<string, set<string>> m;
//         for (auto account : accounts) {
//             for (int i = 1; i < account.size(); ++i) {
//                 root[account[i]] = account[i]; // a->a, b->a, c->a d->d, e->d, f->d, g->g, b->g, d->g
//                 owner[account[i]] = account[0];
//             }
//         }
//         // 这里开始连上了
//         for (auto account : accounts) {
//             string p = find(account[1], root);
//             for (int i = 2; i < account.size(); ++i) {
//                 root[find(account[i], root)] = p; // g->a
//             }
//         }
//         for (auto account : accounts) {
//             for (int i = 1; i < account.size(); ++i) {
//                 m[find(account[i], root)].insert(account[i]);
//             }
//         }
//         for (auto a : m) {
//             vector<string> v(a.second.begin(), a.second.end());
//             v.insert(v.begin(), owner[a.first]);
//             res.push_back(v);
//         }
//         return res;
//     }
//     string find(string s, unordered_map<string, string>& root) {
//         return root[s] == s ? s : find(root[s], root);
//     }
// };

// LC 721 变种

// #include <iostream>
// #include <vector>
// #include <unordered_map>
// #include <unordered_set>
// #include <queue>
// #include <string>

// using namespace std;

// void bfs(const string& user, const unordered_map<string, unordered_set<string>>& email_to_users, unordered_set<string>& visited, unordered_set<string>& component, const unordered_map<string, unordered_set<string>>& user_to_emails) {
//     queue<string> q;
//     q.push(user);

//     while (!q.empty()) {
//         string node = q.front();
//         q.pop();

//         if (visited.find(node) == visited.end()) {
//             visited.insert(node);
//             component.insert(node);
//             for (const auto& email : user_to_emails.at(node)) {
//                 for (const auto& neighbor : email_to_users.at(email)) {
//                     if (visited.find(neighbor) == visited.end()) {
//                         q.push(neighbor);
//                     }
//                 }
//             }
//         }
//     }
// }

// vector<unordered_set<string>> groupUsersByEmail(const vector<vector<string>>& input) {
//     unordered_map<string, unordered_set<string>> user_to_emails;
//     unordered_map<string, unordered_set<string>> email_to_users;

//     // Process the input
//     for (const auto& row : input) {
//         string user = row[0];
//         for (size_t i = 1; i < row.size(); ++i) {
//             string email = row[i];
//             user_to_emails[user].insert(email);
//             email_to_users[email].insert(user);
//         }
//     }

//     unordered_set<string> visited;
//     vector<unordered_set<string>> components;

//     // Iterate through each user to find connected components
//     for (const auto& [user, _] : user_to_emails) {
//         if (visited.find(user) == visited.end()) {
//             unordered_set<string> component;
//             bfs(user, email_to_users, visited, component, user_to_emails);
//             components.push_back(component);
//         }
//     }

//     return components;
// }

// int main() {
//     vector<vector<string>> input = {
//         {"A1", "alice@yahoo.com", "alice_1@gmail.com"},
//         {"A2", "bob@facebook.com"},
//         {"A3", "alice_1@gmail.com", "alice_2@hotmail.com"},
//         {"A4", "alice_2@hotmail.com"},
//         {"A5", "bob@facebook.com"},
//         {"A6", "carol@gmail.com"}
//     };

//     vector<unordered_set<string>> components = groupUsersByEmail(input);

//     // Print the result
//     cout << "((";
//     for (size_t i = 0; i < components.size(); ++i) {
//         cout << "(";
//         auto it = components[i].begin();
//         while (it != components[i].end()) {
//             cout << *it;
//             if (++it != components[i].end()) cout << ",";
//         }
//         cout << ")";
//         if (i != components.size() - 1) cout << ", ";
//     }
//     cout << "))" << endl;

//     return 0;
// }

54998