medium Number of Provinces

Problem Statement

There are n cities. Some of them are connected in a network. If City A is directly connected to City B, and City B is directly connected to City C, city A is indirectly connected to City C.

If a group of cities are connected directly or indirectly, they form a province.

Given an n x n matrix isConnected where isConnected[i][j] = 1 if the i^th city and the j^th city are directly connected, and isConnected[i][j] = 0 otherwise, determine the total number of provinces.

Examples

• Example 1:
  • Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]

• Expected Output: 2

• Justification: Here, city 1 and 2 form a single provenance, and city 3 is one province itself.

• Example 2:

  • Input: isConnected = [1,0,0],[0,1,0],[0,0,1]]

• Expected Output: 3

• Justification: In this scenario, no cities are connected to each other, so each city forms its own province.

• Example 3:

  • Input: isConnected = [[1,0,0,1],[0,1,1,0],[0,1,1,0],[1,0,0,1]]

• Expected Output: 2
• Justification: Cities 1 and 4 form a province, and cities 2 and 3 form another province, resulting in a total of 2 provinces.

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

Solution

To solve this problem, we'll employ the Union-Find algorithm, a powerful algorithm for managing disjoint sets. The essence of the approach is to group cities into sets, where each set represents a connected province.

Initially, every city is considered its own province. As we go through the matrix, we use Union operations to join cities that are directly connected, effectively merging their sets. The Find operation identifies the representative of each set (or province) and helps in determining if two cities are already in the same province. By iteratively applying Union operations to all connected city pairs, we merge their respective sets.

In the end, the number of distinct sets (or provinces) is determined by counting the unique representatives of each set, providing the solution to our problem. This approach ensures efficient handling of connections and an accurate count of disconnected provinces.

Step-by-Step Algorithm

1. Initialization:

   • Create a Union-Find data structure with parent and rank arrays.
   • Initialize the parent array such that each node is its own parent.
   • Initialize the rank array with zeros.

2. Process the Connections:

   • For each pair of nodes (i, j) in the adjacency matrix isConnected:
     • If isConnected[i][j] is 1, indicating a direct connection:
       • Use the find operation to check the roots of nodes i and j.
       • If the roots are different, decrement the numberOfProvinces and perform the union operation to merge the sets containing nodes i and j.

3. Return the Result:

   • The final value of numberOfProvinces represents the number of connected components or provinces.

Algorithm Walkthrough

Given an input isConnected = [[1,1,0],[1,1,0],[0,0,1]], let's walk through the algorithm:

Initial Setup

1. Initialization:

   • parent = [0, 1, 2] (each node is its own parent)
   • rank = [0, 0, 0] (initial ranks are zero)
   • numberOfProvinces = 3 (initially, each node is its own province)

2. First Node (i = 0):

   • (i = 0, j = 1):
     • isConnected[0][1] = 1 (nodes 0 and 1 are connected)
     • find(0) returns 0 (root of 0)
     • find(1) returns 1 (root of 1)
     • Roots are different, so decrement numberOfProvinces to 2.
     • Perform union_set(0, 1):
       • find(0) returns 0
       • find(1) returns 1
       • rank[0] == rank[1], so attach root of 1 to root of 0 and increment rank[0].
       • Updated parent = [0, 0, 2] and rank = [1, 0, 0].

1. Second Node (i = 1):
   • (i = 1, j = 2):
     • isConnected[1][2] = 0 (nodes 1 and 2 are not connected)
     • No action needed.

1. Third Node (i = 2):
   • No connections to check (as j only goes from i+1 to n).

• The final count of provinces is 2.

Code

Complexity Analysis

Time Complexity

1. Initialization:

   • Initializing the parent and rank arrays takes time, where (N) is the number of nodes (or cities).

2. Find Operation:

   • The find operation with path compression has an amortized time complexity of , where is the inverse Ackermann function. This function is extremely slow-growing and can be considered nearly constant for practical input sizes.

3. Union Operation:

   • The union_set operation involves two find operations and one assignment, leading to a time complexity of per union.

4. Processing Connections:

   • The nested loops iterate through each pair of nodes to check for connections. This involves iterations, where each iteration involves at most two find operations and one union_set operation. Thus, the total time complexity for processing all connections is .

Given that is nearly constant, the overall time complexity can be simplified to .

Space Complexity

1. Parent and Rank Arrays:
   • The parent and rank arrays require space each, where (N) is the number of nodes.

Alternate Approach (Using DFS)

At a high level, the problem of identifying provinces in the given matrix can be visualized as detecting connected components in an undirected graph. Every city represents a node, and a direct connection between two cities is an edge. The number of separate, interconnected clusters in this graph is essentially the number of provinces. To navigate this graph and identify these clusters, we employ the Depth First Search (DFS) technique, marking visited nodes (cities) along the way.

Step-by-step Algorithm

1. Initialization:

   • Initialize an integer variable provinces to 0. This will count the number of distinct provinces.
   • Create a visited array of the same size as the number of cities (isConnected.size()), initialized to false. This array keeps track of whether a city has been visited.

2. Iterate Over Each City:

   • Loop through each city i from 0 to n-1 (where n is the number of cities).
   • For each city i, check if it has been visited. If not, it indicates the start of a new province.
   • Increment the provinces counter, as this city marks the start of a new province.
   • Call the dfs method to explore all cities connected to city i.

3. Depth-First Search (DFS):

   • In the dfs method, start with city i.
   • Loop through each city j from 0 to n-1.
   • If city i is connected to city j (isConnected[i][j] == 1) and city j has not been visited (!visited[j]), mark city j as visited (visited[j] = true).
   • Recursively call the dfs method with city j as the new starting point to explore all its connected cities.

4. Repeat DFS for Each Province:

   • Once the DFS completes for a city, return to the main loop in the findCircleNum method and continue with the next unvisited city.
   • Repeat this process until all cities have been visited.

5. Return the Number of Provinces:

   • After all cities have been checked, return the value of provinces, which now holds the total number of distinct provinces.

Algorithm Walkthrough

Let's walk through the algorithm using the example vector<vector<int>> example1 = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}.

Matrix Representation:

   0  1  2
0 [1, 1, 0]
1 [1, 1, 0]
2 [0, 0, 1]

Here:

• City 0 is connected to City 1.
• City 2 is isolated.

Step 1: Initialization

• provinces = 0
• visited = [false, false, false] (Initially, no city is visited)

Step 2: First Iteration (i = 0)

• Check if City 0 has been visited: visited[0] == false.
• Since City 0 has not been visited, initiate DFS starting from City 0.
• Increment the province count: provinces = 1.

Step 3: DFS for City 0

• Mark City 0 as visited: visited[0] = true → visited = [true, false, false].
• Check the connection between City 0 and other cities:
  • City 0 to City 0: Already visited or same city, so skip.
  • City 0 to City 1: isConnected[0][1] == 1 and visited[1] == false.
    • Mark City 1 as visited: visited[1] = true → visited = [true, true, false].
    • Perform DFS for City 1.

Step 4: DFS for City 1

• Check the connection between City 1 and other cities:
  • City 1 to City 0: Already visited, so skip.
  • City 1 to City 1: Already visited or same city, so skip.
  • City 1 to City 2: isConnected[1][2] == 0, so skip.
• DFS completes for City 1, backtrack to complete DFS for City 0.

Step 5: Complete DFS for City 0

• All connected cities for City 0 are visited. DFS for City 0 is complete.

Step 6: Second Iteration (i = 1)

• Check if City 1 has been visited: visited[1] == true.
• Since City 1 is already visited, skip DFS and move to the next iteration.

Step 7: Third Iteration (i = 2)

• Check if City 2 has been visited: visited[2] == false.
• Since City 2 has not been visited, initiate DFS starting from City 2.
• Increment the province count: provinces = 2.

Step 8: DFS for City 2

• Mark City 2 as visited: visited[2] = true → visited = [true, true, true].
• Check the connection between City 2 and other cities:
  • City 2 to City 0: isConnected[2][0] == 0, so skip.
  • City 2 to City 1: isConnected[2][1] == 0, so skip.
  • City 2 to City 2: Already visited or same city, so skip.
• DFS completes for City 2.

Step 9: Completion

• All cities have been visited. The total number of provinces is 2.

Final Output:

• The algorithm returns 2, indicating there are 2 distinct provinces in the given example.

Code

Time Complexity

• Depth First Search (DFS): For a given node, the DFS will explore all of its neighbors. In the worst case, we may end up visiting all nodes in the graph starting from a single node. Hence, the DFS complexity is , where (n) is the number of nodes.

• Overall Time Complexity: For each node, we might call DFS once (if that node is not visited before). Thus, the overall time complexity is , with the DFS call being nested inside a loop that iterates over all nodes. In dense graphs where each node is connected to every other node, we will reach this upper bound.

Space Complexity

• Visited Array: This is an array of size (n) (the number of nodes), so its space requirement is .
• Recursive Call Stack: In the worst case, if all cities are connected in a linear manner (like a linked list), the maximum depth of recursive DFS calls will be (n). Hence, the call stack will take space.
• Overall Space Complexity: The dominant space-consuming factors are the visited array and the recursive call stack. Hence, the space complexity is .