Last Updated: 30 Mar, 2021
The Earliest Moment When Everyone Become Friends
Hard
Asked in companies
In a social group, there are ‘N’ people, with unique integer ids from 0 to (N - 1). We have an array of ‘logs’, where each logs[i] = [timestamp, idA, idB] contains a non-negative integer ‘timestamp’ and the ‘ids’ of two different people.
Each log represents the time in which two different people became friends.
Let’s say that person A is acquainted with person B if A is friends with B, or A is a friend of someone acquainted with B. Your task is to return the earliest time every person became acquainted with every other person.
Note:
1) The ids are 0-indexed.
2) Friendship is symmetric here. That is, if A is friends with B, then B is friends with A.
3) Return -1 if there is no such earliest time.
For example:
Given ‘logs’ =[[2, 0, 1],[3, 1, 2],[4, 2, 3]].
The answer here would be 4 :
When the people with id 2 and 3 become friends, then the circle gets completed, and the time among them is 4, and because 4 is the largest time among all, the time for the circle to get completed is 4.
Input format:
The first line of input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains two integers, ‘N’, representing the number of ‘ids’ people, and ‘M’ which denotes the number of ‘logs’.
The following ‘M’ lines of each test case contain exactly three integers, denoting the 'time', 'idA', and 'idB'.
Output format:
For each test case, print a single line containing a single integer denoting the minimum time for the connection to get complete.
The output of each test case will be printed in a separate line.
Note :
You don't have to print anything. It's been already taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 150
1 <= M <= 300
Where ‘T’ is the number of test-cases and, ‘N’ is the number of people, and ‘M’ is the number of logs.
Time limit: 1 second
Approaches
The main idea is to sort the logs in increasing order of the time between the two ids.
Then use DSU to make a connection and find the connected component.
The main idea is to use a DSU data structure to find connected components. A DSU data structure can be used to maintain knowledge of the connected components of a graph and query for them quickly. In particular, we would like to support two operations:
- find(node x), which outputs a unique id so that two nodes have the same id if and only if they are in the same connected component, and:
- union(node x, node y), which draws an edge (x, y) in the graph, connecting the components with id find(x) and find(y) together.
The moment we get the full circle, we can return that time.
- Sort the ‘logs’ array in increasing order based on the ‘time’ variable.
- This can be done by passing a comparator that compares vectors a and b and return the bool value of a[0] < b[0].
- We will maintain a variable ‘circle’ which tells us how much of the connected component has formed. Initially, circle = ‘N.’
- Traverse the logs and make connections between the two ids if they have a different parent. We can find the parents of the current node by using the helper function ‘findParent.’
- findParent take two inputs:
- The node, for which we need to find parent
- The parent array, which stores the parent of all nodes.
- If the parent[i] = i , then we return i .
- findParent take two inputs:
- If they have different parents, we will union them, using the function ‘unionIt and reduce the circle by 1.
- Union It works in the following way :
- It takes three input :
- Node1
- Node2
- The parent array, which stores the parent of all nodes.
- It assigns parent[node2] = node1
- It takes three input :
- The state when we get circle = 1. We return the time because that is the moment the circle gets complete, and hence we get the maximum time.
Similar problems