I was recently asked this problem in my online assessment, and i couldn't understand the explanation provided in the problem statement. can someone please help. Also give me some insights to solve this. Thanks :)

Connected component of a directed graph G=(V,E) is a maximal set of vectces C ⊆ V such that for every pair of vertices u and v in C , vertices u and v are reachable from each other.

Given an integer N-number of vertices and an adjacency matrix of size NxN . The adjacency matrix represents the edges of a directed non weighted graph.

Find two connected components that have the maximum number of vertices . Find minimum list of vertiecs(valid path) that connect two connected components.

Rules :

1. All edges of the graph have unit distance.

2. There are no negative edges in graph.

3. If there is more than one path between two connected components having same length , then print the one with extreme vertices(Try to solve using dynamic programming).

4. Components could be single vertex also. If both components are single vertices , then path is represented by the maximum list of vertices(path) thta connect two extreme ends of vertices.

5. If the two connected components haev the same number of vertices(>1) , then print the vertices of components in the order of appearance in adjacency matrix.

6. If the two connected components have the same number of vertices (= 1) , and need to select one among them , then the vertex at extreme end of graph will be given preference.

7. All the vertices of connected components and paths are printed in ascending order.

Constraints:

1. N>2

2. Isolated nodes are not considered.

3. There is atleast one path between largest and second largest connected components.

Input Format :

First line of input contains an integer N , which is the number of vertices in the graph.

Then there are N lines having N integers each , seperated by single white space. This is the adjacency matrix where the integers have value 0 or 1.

Output Format:

First line has integers , seperated by single white space, where each integer denotes the vertex of the largest size connected component.

Second line has integers , seperated by single white space, where each integer denotes the vertex of the second largest size connected component.

The third line has integers , seperated by single white space, where integers denote a valid path between the largest and second largest components .

Sample Input 1 :

5

0 0 1 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

Sample Output :

0 1 2
4
0 3 4

Explanation : N=5 . Graph has 5 vertices with 5 edges 0->2,0->3,1->0,2->1 and 3->4.

Connected components are {0,1,2} ,{3},{4}.

We have to find two components with maximum number of vertices . Largest size component {0,1,2} First component has 3 vertices . Since {3} and {4} have only one vertex and we need to find the farthest one from these , we select {4} as second largest component. The path that connects these two components is : 0->3->4.

Sample Input 2:

1

0 0 1 1 0
1 0 0 0 1
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

Sample Ouput 2:

0 1 2
4
1 4