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 :
All edges of the graph have unit distance.
There are no negative edges in graph.
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).
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.
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.
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.
All the vertices of connected components and paths are printed in ascending order.
Constraints:
N>2
Isolated nodes are not considered.
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
nvm, i solved it. Thanks for your time ;)
Hey how you solved it. For first part it could be solved with Kosarajus Algo. For 2nd part what you did.
And what is extreme vertex.