The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows. The first input line of each test case contains an integer ‘N’ denoting the number of accounts. Each of the next ‘N’ lines contains space-separated strings where the first string denotes the account holder’s name, and the rest of the strings represent the email addresses.
For each test case, print the number of accounts after merging in the first line and then print the space-separated name and email address associated with each account in a separate line. Print the output of each test case in a separate line.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= T <= 50 1 <= N <= 100 1 <= |accounts[i]| <= 10 1 <= |accounts[i][j]| <= 30 Time limit: 1 sec
The basic idea of this approach is to model this problem as a graph problem. Let us create a graph of emails with an edge between two emails if they occur in the same account.
The figure below shows the graph constructed for the first test case of sample test case 1.
We can observe that the set of accounts which needs to be merged will be a part of connected components. So the problem is now reduced to finding the connected components in an undirected graph. We can easily get the connected component by doing a depth-first search of the graph. You can refer to this tutorial of cp-algorithms for a more detailed explanation. Search for connected components in a graph - https://cp-algorithms.com/graph/search-for-connected-components.html#:~:text=Given%20an%20undirected%20graph%20G,path%20exists%20between%20different%20groups.
Let unordered_map<string, string> ‘EMAIL_TO_NAME’ be HashMap to store the mapping of emails to the name of the person having it. This mapping will help us in getting the name of the person while creating the merged accounts.
And also let unorderd_map<string, vector<string>> ‘GRAPH’ stores the adjacency list of the constructed graph.
Now the consider the following steps :
Longest Subarray With Zero Sum
Distance to a Cycle in Undirected Graph
Merge Two Sorted Arrays Without Extra Space
Ninja And The Strictly Increasing Array
Negative To The End