547. Number of Provinces

#graph #dfs #union-find

Problem

Number of Provinces - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

DFS

class Solution {
    public int findCircleNum(int[][] isConnected) {
      // V -> Vertices E -> Edges. But in this case  V = E
      // In the worst case, the DFS algorithm visits all the cities in the graph, which takes O(n) time, where n is the number of cities.
      //In the worst case, each city is connected to all other cities, resulting in a complexity of O(n) for checking the connected cities in total.
      // Therefore the time complexity is O(N^2)
      // Time Complexity : O(N^2)
      // Space Complexity : O(N), to keep track of visited arrays using boolean[]
      
      // The given input is in the form of adjacent matrix
      if(isConnected ==null) {
          return 0;
      }
      int n = isConnected.length; // N = Number of cities
      int count = 0; // Number of provinces
      boolean[] visited = new boolean[n]; // Keep track of visited cities
      
      for(int city=0;city<n;city++) { // Iterate through all cities
          if(!visited[city]) { // If city is not explored
            dfs(city, visited, isConnected); // Explore
            count++; // Increment the count
          }
      }
      return count;
    }

    private void dfs(int city, boolean[] visited, int[][] graph) {
      // Standard DFS
      visited[city] = true;

      for(int neighboringCity=0;neighboringCity<graph.length;neighboringCity++) {
        // Graph[city][neighboringCity] == 1 --> The city and neighboringCity are connected
        // And the neighboringCity is not explored
        if(graph[city][neighboringCity]==1 && !visited[neighboringCity]) {
            dfs(neighboringCity, visited, graph);
        }
      }
    }
}

Union Find