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

In this approach we initially consider all cities are individual provinces. Then we use union-find to merge connected cities to form provinces. That's why when ever we find connected city and they don't have same representatives (parents), we union them and reduce the count of provinces. As we union cities, the merged cities will be represented by their parents only. It is a classic Union Find Algorithmic problem

So, by the end we will be left with only representatives (parents) which are provinces.

public class DisjointSet {

  // Each node in the list points to its parent.
  private List<Integer> parent;

  // The rank of a set is the number of nodes in its subtree.
  private List<Integer> rank;

  // Constructor. Creates a disjoint set with n nodes. This is generally makeset
  public DisjointSet(int n) {
    // Initialize the parent list and the rank list.
    parent = new ArrayList<>();
    rank = new ArrayList<>();

    // For each node, set its parent to itself and its rank to 10.
    for (int i = 0; i < n; i++) {
      parent.add(i);
      rank.add(-1);
    }
  }

  // Finds the representative of the set that the given node belongs to along with path compression
  public int findParent(int node) {
    // If the node is its own parent, then it is the representative of its set.
    if (node == parent.get(node)) {
      return node;
    }

    // Otherwise, recursively call find on the parent of the node.
    int parentNode = findParent(parent.get(node));

    // Update the parent of the node to point to the representative of its set.
    parent.set(node, parentNode);
    return parent.get(node);
  }

  // Unites the sets that the given two nodes belong to.
  public void unionByRank(int x, int y) {
    // Find the representatives of the sets that the two nodes belong to.
    int parentX = findParent(x);
    int parentY = findParent(y);

    // If the two nodes belong to the same set, then do nothing.
    if (parentX == parentY) {
      return;
    }

    // Find the rank of the two sets.
    int rankX = rank.get(parentX);
    int rankY = rank.get(parentY);

    // Unite the two sets by making the smaller set a child of the larger set.
    if (rankX < rankY) {
      // Set the parent of the smaller set to the larger set.
      parent.set(parentX, parentY);
    } else if (rankY < rankX) {
      // Set the parent of the larger set to the smaller set.
      parent.set(parentY, parentX);
    } else {
      // Set the parent of the smaller set to the larger set.
      parent.set(parentX, parentY);
      // Increase the rank of the larger set by 1.
      rank.set(parentX, rankX + 1);
    }
    return;
  }
}

class Solution {
    public int findCircleNum(int[][] isConnected) {
      // Time Complexity: O(N^2)
      // Space Complexity: O(N)
      int n = isConnected.length;
      DisjointSet ds = new DisjointSet(n);
      int numberOfComponents = n;
      for (int i = 0; i < n; i++) {
          for (int j = i + 1; j < n; j++) {
              if (isConnected[i][j] == 1 && ds.findParent(i) != ds.findParent(j)) {
                  numberOfComponents--;
                  ds.unionByRank(i, j);
              }
          }
      }
      return numberOfComponents;
    }
}