search

abhisek247767 / LeetCode2024-6Companies30Days

Make your first Pull Request on Hacktoberfest 2024. Don't forget to spread love and if you like give us a ⭐️
16 stars 29 forks source link

Total Number of Disjoint Components #21

Closed madhura-ingole closed 1 week ago

madhura-ingole commented 1 week ago

Description This pull request implements a solution for determining the total number of provinces formed by cities represented in an n x n adjacency matrix. Each city is a node, and the direct connections between cities are represented as edges in the matrix. The objective is to count all the provinces, which are groups of directly or indirectly connected cities.

Problem Summary: Input: An n x n matrix isConnected where isConnected[i][j] = 1 indicates a direct connection between city i and city j, and isConnected[i][j] = 0 otherwise. Output: The total number of provinces (disjoint components) in the graph.

Approach: Utilize Depth First Search (DFS) or Breadth First Search (BFS) to traverse the graph. Maintain a visited array to track cities that have already been included in a province. Increment the province count each time a new DFS or BFS is initiated, representing a new province.

abhisek247767 commented 1 week ago

Please read the guidelines. Star the repo and follow me here

madhura-ingole commented 1 week ago

Solved in #22