DAY 32 -Number of Provinces

Hey Guys!, Welcome to another day another question. This is day 32 and I am still consistent to my surprise as well. Incase you don't know what I am doing. My goal is simple , it's to be consistent for a 100 days straight. Each day I solve a walkthrough of a solution to a leetcode question breaking it down as good as I can.

Today we are going to solve a graphs question. So if you guys are unfamiliar with graphs, I suggest you guys first to get a basic understanding of what graphs are.
What are weighted, directed and cyclic/acyclic graphs as they are crucial to understanding a graph problem.
We also need to know what techniques we use to traverse a data structure in the form of graphs.

In case you don't know where to learn from them, I am hereby linking down an article/video for the same.

LINKS:

Graphs
Striver's Video

Question: Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

Example 1:

• Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]
• Output: 2

Example 2:

• Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]
• Output: 3

For a visual image of this question, I am hereby attaching an image.

Approach:

• The question wants us to find out the number of starting points.
• Let's revisit what we did in BFS/DFS approach.
• Our BFS/DFS approach allows us to visit every index that's attached to each other.
• From our starting points, if we do a dfs approach on that node, it will allow us to visit consequent connected nodes and do a dfs on them.
• In the process it will mark them as visited so that we don't run in a loop.
• But If two graphs are not connected indirectly or directly, our dfs on that starting point will never traverse through that.
• Hence we will need to switch our starting Point to that of that node which we can't visit/ not been visited.
• Doing so in the process we will have N starting points which will mean n points from n different graphs from n different provinces.
• Hence We will return that, because that is our answer. No of provinces.

Algorithm:

• Create a variable n to store no of vertices.
• Create a visited array to store the visited vertices.
• Create a variable startingPoints to store our result.
• Iterate through all of the nodes, and for each node i check if it has been visited or not. If node i is not visited, we increment startingPoints by 1 and start a DFS traversal:

Code:

void dfs(int node, vector<vector<int>>& isConnected, vector<int>& visited) {
        visited[node] = true;
        for (int i = 0; i < isConnected.size(); i++) {
            if (isConnected[node][i] && !visited[i]) {
                dfs(i, isConnected, visited);
            }
        }
    }
    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        int startingPoints = 0;
        vector<int> visited(n, 0);

        for(int i = 0; i < n; i++){
            if(!visited[i]){
                startingPoints++;
                dfs(i, isConnected, visited);
            }
        }
        return startingPoints;
    }

Complexity Analysis:

• Time Complexity: O(N^2)
• Space Complexity: O(N)

Thanks for reading. Feedback is highly appreciated!.