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:
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!.
Top comments (0)