You have a map which consists of N points,some pairs of them are connected with unidirectional thread(it means we can move only in the specified direction.Overall there are N-1 threads on the map.
We need to choose a point from the map so that we can get from the chosen point to any another point on the point .For that we may have to inverse some of thread direction.
Tell all the points in the map which requires minimum inversion of thread direction in the given map.
Suppose we select a point P in the map which requires Q inversion of threads in order to reach all the points in the map as given above .
So u need to find all the points for which the number of inversions Q is minimum .
Input :first line has N number of points
next N-1 lines follow U V where there is an edge from U to V
Output: Return all points with minimum inversions such that we can reach all other points
PS:Coding challenge has been finished on interviewbit.
Run dfs from node 1 and count how total forward and backward edges are there(forward means going according to given graph and backward means in opposite direction). For node 1, number of reversal required will be number of backward edges. In the given below image, 1 denotes forward edge and 2 denotes backward edge.
Now run dfs again from node 1, keep count of many forward and backward edges you have used to reach that node.
Observation - For finding how many reversal you need for current node, observe that you just reverse direction of all the edges which are in the path from 1 to current node. So number of reversal required for any node will be
forward_edge_count(because of reversal) +
( total_backward_edges - backward_edges_count ) (other backward edges other than the path)
Note - Since it’s graph, it’s possible that there are more than 1 connected component. In that case, answer will all nodes from 1 to n.
Theres a very simpler solution possible to this.
Take any example of a tree with both forward and backward edges, and then start from any node marking its level as 0, then move forward to its neighbours and increment its level if its on a forward edge, else decrement the level. Traverse the whole tree using dfs just once, using this method and saving the nodes corresponding to their levels in a map (or you can alternatively use an arraylist but then you ll have use modular on indices) .
