DAY 32 -Number of Provinces
Tags: coding, leetcode, tutorial, codenewbie
Published: 2023-07-05 16:33:49

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](https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/)
[Striver's Video](https://youtu.be/M3_pLsDdeuU)

---

## 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!.