DAY 32 -Number of Provinces

Nayan Pahuja - Jul 5 '23 - - Dev Community

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;
    }
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis:

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

Thanks for reading. Feedback is highly appreciated!.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .