Problem Link
PROBLEM NAME :- COVID SHORTAGE AUTHOR :- @twinklesharma
CONTEST :- CLADDING THE CODE
ORGANIZER :- ROBOTICS CLUB MMMUT
Solution
What to Find.
After analysing question it is clear that the main motive of question is to find strongly connected component in Directed graph whose node and edges are given.
If you are confused why, let me show it in question it is given that a truck will distribute the material among all cities, but the condition is to follow common rule of transportation means he can go via only those path which are unbanned means which are given as input as
i j , means there is a path from i to j.
and one more condition is he must have to came back to his ware house means he has to came back to that node from where he is started and in this whole journey your task is to calculate how many cities he can cover. So now it is obvious that he can cover all strongly connected component from that starting node and according to question you are free to start from any node.
How to Find.
As there are various algo to find SCCs, but here i have used Kosaraju’s algorithm
According to this transpose graph (the same graph with the direction of every edge reversed) has exactly the same strongly connected components as the original graph.
So firstly i found DFS on graph and then stored the numbering of finishing vertex in a graph then i transposed the graph and set all the nodes as visited = false and then again i performed DFS on that transposed graph but this time i incremented a counter cities_covered in every time i called the DFS from while loop it checks for nodes in one strongly connected component. finally after checking which SCC contains maximum nodes it prints that maximum number.
Code
Link to Working Code with all 4 Bug Commented
In this Solution there are 4 minor bugs.
Bug Number 1:- This Bug is in Depth First Search Algorithm.
According to DFS for loop checks for all of those nodes in which visited flag is 0 or false but here is different condition.
Bug Number 2:- This Bug is in Transposing the Graph.
Bug Number 4:- This Bug is because of setting some of the nodes already setted as visited Before performing DFS on Graph.
Bug Number 4:- This Bug is Garbage Value error (using variable for comparison before initalization).