Tester: Aditya Sarode
Editorialist: Aditya Sarode
Given a graph with K edges, find out the number of nodes connected to Mr. X such that the friend has the largest network of friends.
Construct graph using adjacency lists, sort the adjacency lists lexicographically, apply DFS to find the sizes of subgraphs connected to Mr. X.
We construct a graph in which the people are nodes and an edge between two nodes represent that the two people are friends.
So the problem is reduced to, given an undirected graph find out the number of nodes of a friend of Mr. X such that the friend has the largest network of friends.
To find the number of people in the network of a friend of Mr. X, we can apply dfs on that particular friend. The dfs would return the number of people in it’s network.
But applying Dfs seperately on each of Mr. X’s friend can result in a TLE, given the limits.
Thus we sort the adjacency list of Mr. X and apply dfs and as we are traversing each node, we mark it as visited. While applying dfs for other friends, we don’t consider them who have already been marked visited.
If two friends of Mr. X are in the same network, initially the one with lexicographically smallest name will be visited and so DFS won’t be applied to the next friend. Both the friends will have the same number of friends in network, but we need to consider the lexicographically smallest, which is achieved by applying DFS in this manner.
The number of nodes are not given, so the nodes must be added dynamically.