Baby Names

1. If John and Jon are synonyms, and Jon and Johnny are synonyms, then John and Johnny are also synonyms. 2. While printing the true frequency, out of the names with synonymic relationships, use the names list first.

Names = 5, Synonyms = 3 5 john 15 jon 12 chris 13 kris 4 christopher 19 3 jon john chris kris chris Christopher The output for the above example will be: john 27 chris 36 Since “jon” and “john” are synonyms, the final true frequency will be 15 + 12 = 27, and since john appears first in the first list, we’ll use “john” as the real name. Also, “chris” and “kris” are synonyms, and since “chris” and “christopher” are also synonyms, “chris” and “christopher” will also be synonyms, and the true frequency will be 13 + 4 + 19 = 36, and since “chris” appears first in the names list, we’ll use it as the real name.

The first line of the input contains an integer 'T' denoting the number of test cases. The first line of each test contains an integer 'N', representing the total number of names. The next 'N' lines contain a string and an integer, representing a name and the number of times this name appears in the list. The next line contains an integer 'M', representing the number of synonym relationships. The next 'M' lines contain two strings that have a synonym relationship.

For Test Case 1: As “john” and “jon” are synonyms of each other. Hence, total frequency will be 15 + 12 = 27. Similarly, “chris,” “kris,” and “christopher” are synonyms, and their total count of frequency will be 13 + 4 + 19 = 36.

Connected Components

Approach: We can visualize this question as a graph where each name will represent a particular node, and synonymic relations will connect two nodes. Each connected component of this graph will represent synonyms of a specific name. We will traverse through each connected component using DFS.

Algorithm:

For simplicity, we will represent names as numbers, i.e., 1 to ‘N’, and make an adjacency list ‘ADJ’ for storing the graph.
We will maintain an array ‘VISITED’ to check whether the node has been visited or not.
We will check each node from 1 to N whether it is visited or not, and if it is not visited, we’ll perform a DFS on it.
While doing DFS at a particular node, we will mark that node as visited, and we will traverse all the unvisited nodes connected to this node.
At each step of DFS, we will also consider the frequencies of the nodes (as given in the question - frequency of strings) that we are traversing. After traversing all the unvisited nodes connected to the current node at which we are, we will have a count of total frequencies.
When we have visited all the nodes of a connected component, we will have a total count of frequencies.
Hence, the answer will be the node from which are performing DFS, and the DFS will give the total count of the frequency.
Similarly, we will find the answers of the other connected components also.

Time Complexity

O(N + M), where N is the number of different names and M is the number of relations.

Making an adjacency matrix will take O(N + M) time, and DFS takes O(N + M) time too. Hence, the overall complexity will be O(N + M).

Space Complexity

O(N + M), where N is the number of different names and M is the number of relations.

The adjacency matrix will take O(N + M). Hence, the space complexity will be O(N + M).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation Of Sample Input 1:

Sample Input 2:

Sample Output 2:

Explanation Of Sample Input 2: