PROBLEM LINK:
Vatsal and his Bae
Author, Tester, Editorialist: Dipen Ved
Under KJSCE CODECELL
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
Given an unweighted directed graph with Q nodes and P edges, for each node i , tell whether it is part of a cycle or not.
QUICK EXPLANATION:
You can find the no of routes from X to Y, through Z, first by counting no of routes from of X to Z with
depth i where 1<=i<=k-1 Then you count the number of routes from Z to Y, with depth (k-i) where 1<=i<=k-1
and multiply both these numbers, to get total routes no of routes from X to Y through Z.
EXPLANATION:
Naive Solution O(Q.P) :
One way to solve this problem could be that for each node i, We perform a dfs with i as root and check if a back edge comes from any other vertex in the graph to node i. If yes, the node will be a part of a cycle otherwise not. Since for each node we perform a dfs, the complexity will be O(Q*P) and would time out.
Faster Solution O(P+Q) :
Instead of performing a dfs for every node, we could find the strongly connected components (scc) of the given graph. If the size of an scc is greater than 1, the answer for all the nodes in that scc will be yes. This would work because an scc can be imagined as one or more directed cycles attached to each other by sharing common vertices. Hence, each vertex in an scc of size greater than 1 will be a part of a cycle. The scc’s can be found by using any one of the two standard algorithms : Kosaraju or Tarjan’s algorithm.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solution can be found here.