DEV Community

Cover image for DAY 32 -Number of Provinces
Nayan Pahuja
Nayan Pahuja

Posted on

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

Complexity Analysis:

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

Thanks for reading. Feedback is highly appreciated!.

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay