New update is available. Click here to update.

Last Updated: 12 Mar, 2021

Difficulty: Moderate

```
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 every test case, print a new list of names with their true frequencies.
Print the output of each test case in a separate line.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N, M <= 10^4
1 <= |Name| <= 10
1 <= Frequency <= 100
Where “Name” contains only lowercase English alphabets.
Time limit: 1 sec
```

**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’
- 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.

SIMILAR PROBLEMS

Cakes

Posted: 23 Sep, 2022

Difficulty: Easy

1-3 Palindrome

Posted: 4 Oct, 2022

Difficulty: Easy

Longest Subarray With Zero Sum

Posted: 3 Nov, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Maximum GCD

Posted: 8 Dec, 2022

Difficulty: Hard

Popular Interview Problems: