Approaches To Problem Solving #15(Graph | SCC)

Photo by Jaromír Kavan

Problem : You are given N cities represented as integers and a list of one-way roads that connects one city to another. Return whether you can reach one city from any city.

Let us consider an example to understand the problem better,

Fig-1: Taken From BinarySearch

In the majority of the cases when we are dealing with cities and one-way or two-way roads, it helps to think about the problem as a Graph theory problem.

Since we are concerned about reaching all the cities starting from any random city, it is pretty intuitive to think of the desired solution as a single component that accommodates all the nodes from 0 to N — 1, where ‘N’ is as given in the problem.

But, is it sufficient for all of the cities to belong to the same component, in order to prove that all the cities can be reached from any city picked at random? The answer is NO. Why? Let us consider an example given below,

Fig-2: Example of a Connected but not Strongly Connected Component

Here, all 3 cities belong to the same component but, we cannot reach city ‘A’ from any other city. Hence, we need some addition to our given algorithm of connected components. The missing enhancement that we seek is the concept of Strongly Connected Components (SCC). Consider the following,

Fig-3: Example of a Strongly Connected Component

Approach #1: We can break our solution into two steps:-

Step #1: Checking if all the cities belong to a single connected component.

Step #2: Checking if the connected component consisting of all the N cities is a strongly connected component or not.

If any of the above steps give us FALSE as a result, then the answer is FALSE and is TRUE otherwise.

We can verify the first step by choosing a node or city, arbitrarily, as the source city and performing a DFS. If all the cities are visited, after the DFS traversal is complete, we can be assured that all of the cities belong to a single component.

In order to perform a check on the second step, we need to make some enhancements in our dfs traversal performed earlier. We use Kosaraju’s Algorithm, and maintain a Stack along with our DFS traversal. Once a city or node has been completely explored, we push that city onto the Stack. How does this Stack help us? The Stack tells us about the sequence in which we performed our DFS traversal.

Verifying the second step involves reversing all the edges. Why? Because, if we can reach all the nodes after reversing all the edges by traversing through in the same sequence as we did on our first DFS traversal, we can be sure that collective directions of the edges do not matter and thus, we can always find a way of reaching a destination city, starting from any other city in this component.

Again, if any of the above steps return FALSE as a response, the answer is FALSE and TRUE otherwise.

The time complexity for this solution is ~O(N), where N is the number of cities.

In our next article, one of the problems that we are going to discuss is given below,

Problem: Given the strings “A” and “B” consisting of lowercase alphabet characters, return the number of subsequences of “A” that are equal to “B”. Mod the result by 10**9 + 7.

We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Graph, Connected Components and Strongly Connected Components further!

We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.

For hugs and bugs, please comment down below. Till then.. Happy Coding!

This is the 15th article of the “Approaches To Problem Solving” series.

More such posts can be found at :-

Approaches To Problem Solving #14(Divide and Conquer | DP | Array)

Approaches To Problem Solving : Applying Dynamic Programming on 2-D Matrices

Approaches To Problem Solving #12(String | DP)