Leetcode Problem 547. Number of Provinces

547. Number of Provinces

Leetcode Solutions

Depth First Search (DFS) to Find Number of Provinces

  1. Initialize a count numberOfProvinces to 0 to keep track of the number of provinces found.
  2. Create a boolean array visited to keep track of visited cities, initialized to false.
  3. Iterate over each city i from 0 to n - 1: a. If city i is not visited, increment numberOfProvinces by 1. b. Call the dfs function with the current city i to mark all cities in the current province as visited.
  4. The dfs function: a. Mark the current city as visited. b. Iterate over all cities j and perform a DFS for any city directly connected to the current city and not yet visited.
  5. Return numberOfProvinces as the final result.
UML Thumbnail

Union-Find to Find Number of Provinces

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...