Number of Provinces

▶

Steps

setup

Initialize variables and graph structure

We determine the number of cities (n=3) and create an empty adjacency list for each city.

💡 Setting up adjacency lists prepares for efficient graph traversal instead of repeatedly checking the matrix.

Line:

n = len(isConnected)
graph = [[] for _ in range(n)]

💡 Adjacency lists will represent the graph connections more efficiently for DFS.

fill_row

Start building adjacency list for city 0

We examine connections from city 0 to all other cities to build its adjacency list.

💡 This step shows how the adjacency matrix is converted row by row into adjacency lists.

Line:

for j in range(n):
    if isConnected[0][j] == 1 and 0 != j:
        graph[0].append(j)

💡 City 0 is connected to city 1, so city 1 will be added to city 0's adjacency list.

fill_row

Build adjacency list for city 1

We examine connections from city 1 to all other cities to build its adjacency list.

💡 Continuing adjacency list construction for the next city.

Line:

for j in range(n):
    if isConnected[1][j] == 1 and 1 != j:
        graph[1].append(j)

💡 City 1 is connected to city 0, so city 0 will be added to city 1's adjacency list.

fill_row

Build adjacency list for city 2

We examine connections from city 2 to all other cities to build its adjacency list.

💡 Final adjacency list construction for the last city.

Line:

for j in range(n):
    if isConnected[2][j] == 1 and 2 != j:
        graph[2].append(j)

💡 City 2 has no connections to other cities, so its adjacency list remains empty.

setup

Initialize visited array

Create a visited list to track which cities have been explored during DFS.

💡 Tracking visited cities prevents revisiting and infinite loops during DFS.

Line:

visited = [False] * n

💡 Initially, no city is visited, so all are False.

traverse

Start DFS from city 0

Since city 0 is unvisited, we start DFS from city 0, marking it as processing.

💡 Starting DFS explores all cities connected to city 0, identifying one province.

Line:

if not visited[0]:
    dfs(0)
    provinces += 1

💡 Each DFS call corresponds to discovering a new province.

traverse

DFS explores neighbor city 1 from city 0

From city 0, DFS visits its neighbor city 1, marking city 1 as processing and traversing the edge 0→1.

💡 DFS explores all connected neighbors recursively to find the full province.

Line:

for neighbor in graph[city]:
    if not visited[neighbor]:
        dfs(neighbor)

💡 Edges traversed during DFS show the path of exploration within a province.

compare

DFS explores neighbor city 0 from city 1 but skips it

From city 1, DFS sees neighbor city 0 but skips it because city 0 is already visited.

💡 Avoiding revisiting prevents infinite loops and redundant work.

Line:

if not visited[neighbor]:
    dfs(neighbor)

💡 Visited checks ensure DFS only explores new nodes.

traverse

Finish DFS for city 1 and backtrack to city 0

City 1 has no more unvisited neighbors, so DFS marks city 1 as done and backtracks to city 0.

💡 Backtracking happens when all neighbors are explored, completing one branch of DFS.

Line:

visited[city] = True

💡 Marking nodes done indicates full exploration of their connected component.

traverse

Finish DFS for city 0

City 0 has no more unvisited neighbors, so DFS marks city 0 as done, completing the first province.

💡 Completing DFS for the first city identifies one full province.

Line:

visited[city] = True

💡 All cities connected to city 0 are now visited, representing one province.

compare

Check city 1 for DFS start

City 1 is already visited, so DFS does not start here again.

💡 Skipping visited cities avoids counting the same province multiple times.

Line:

if not visited[city]:

💡 Visited array prevents redundant DFS calls.

traverse

Start DFS from city 2

City 2 is unvisited, so we start DFS from city 2, marking it as processing.

💡 This DFS call discovers the second province consisting of city 2 alone.

Line:

if not visited[city]:
    dfs(city)
    provinces += 1

💡 Isolated cities form provinces of size one.

traverse

City 2 has no neighbors to explore

DFS checks city 2's adjacency list, which is empty, so no further exploration happens.

💡 No neighbors means DFS finishes immediately for isolated city.

Line:

for neighbor in graph[city]:

💡 Empty adjacency list means isolated node forms its own province.

traverse

Finish DFS for city 2

DFS marks city 2 as done, completing exploration of the second province.

💡 Completing DFS here confirms city 2 is a separate province.

Line:

visited[city] = True

💡 DFS completion marks full exploration of a province.

reconstruct

All cities visited, return province count

All cities have been visited; the total number of provinces counted is 2.

💡 The final count reflects the number of connected components found by DFS.

Line:

return provinces

💡 The answer is the number of DFS calls started on unvisited cities.

from typing import List

def findCircleNum(isConnected: List[List[int]]) -> int:
    n = len(isConnected)  # STEP 1
    graph = [[] for _ in range(n)]  # STEP 1
    for i in range(n):  # STEP 2-4
        for j in range(n):
            if isConnected[i][j] == 1 and i != j:
                graph[i].append(j)

    visited = [False] * n  # STEP 5

    def dfs(city: int):  # STEP 6-14
        visited[city] = True  # STEP 6,9,10,14
        for neighbor in graph[city]:  # STEP 7,8,13
            if not visited[neighbor]:
                dfs(neighbor)

    provinces = 0
    for city in range(n):  # STEP 6,11,12
        if not visited[city]:
            dfs(city)
            provinces += 1
    return provinces  # STEP 15

if __name__ == '__main__':
    matrix = [[1,1,0],[1,1,0],[0,0,1]]
    print(findCircleNum(matrix))  # Output: 2

📊

Number of Provinces - Watch the Algorithm Execute, Step by Step

Watching each step of DFS traversal and adjacency list construction reveals how connected components are identified, which is the core of this problem.

Visiting: none

0

1

2

Visiting: 0

Edge: 0 → 1

0

1

2

Visiting: 1

Edge: 1 → 0

0

1

2

Visiting: 2

0

1

2

Visiting: none

0

1

2

Visiting: 0

0

1

2

Queue / Stack

0

Visiting: 1

Edge: 0 → 1

0

1

2

Queue / Stack

01

Visiting: 1

Edge: 1 → 0

0

1

2

Queue / Stack

01

Visiting: 0

0

1

2

Queue / Stack

0

Visiting: none

0

1

2

Visiting: 1

0

1

2

Visiting: 2

0

1

2

Queue / Stack

2

Visiting: 2

0

1

2

Queue / Stack

2

Visiting: none

0

1

2

Visiting: none

0

1

2

Key Takeaways

✓ DFS traversal discovers connected components representing provinces.

Reading code alone hides how DFS explores neighbors recursively; visualization shows the exact order and marking.

✓ Adjacency list conversion simplifies repeated neighbor checks during DFS.

Seeing adjacency lists built step-by-step clarifies why they are more efficient than matrix lookups.

✓ Visited array prevents revisiting nodes and infinite loops.

Visualizing visited states and skipped nodes concretely shows how the algorithm avoids redundant work.

Practice

1. You are given a graph with edges of three types: edges usable by Alice only, edges usable by Bob only, and edges usable by both. The goal is to remove the maximum number of edges while ensuring both Alice and Bob can still traverse the entire graph. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. A greedy approach that processes type 3 edges first using union-find, then type 1 and 2 edges separately.

B. A brute force approach that tries all subsets of edges and checks connectivity for both Alice and Bob.

C. A dynamic programming approach that counts ways to connect nodes with subsets of edges.

D. A shortest path algorithm like Dijkstra's applied separately for Alice and Bob.

Solution

1. Step 1: Understand problem constraints

   The problem requires maximizing edge removals while keeping the graph fully traversable for both Alice and Bob, who share some edges (type 3) and have exclusive edges (type 1 and 2).

2. Step 2: Identify the best approach

   Processing type 3 edges first with union-find maximizes shared connectivity, then adding exclusive edges ensures full connectivity for both. This greedy union-find approach guarantees optimality, unlike brute force (too slow), DP (not applicable), or shortest path (irrelevant).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy union-find with type 3 edges first -> optimal [OK]

Hint: Process shared edges first to maximize connectivity [OK]

Common Mistakes:

• Trying brute force despite exponential complexity
• Ignoring type 3 edges first
• Using shortest path algorithms incorrectly

2. What is the time complexity of the optimal union-find approach for the Swim in Rising Water problem on an n x n grid, where n is the grid dimension?

medium

A. O(n^2 log n) due to sorting all n^2 cells and near-constant union-find operations

B. O(n^4) due to nested loops over grid and union operations

C. O(n^2 * maxElevation) because of simulating water rise for each elevation

D. O(n^2) because each cell is processed once with union-find operations

Solution

1. Step 1: Identify main operations

   Sorting all n^2 cells takes O(n^2 log n^2) = O(n^2 log n). Union-find operations are almost O(1) amortized per union/find.

2. Step 2: Combine complexities

   Total complexity dominated by sorting: O(n^2 log n). Union-find merges add negligible overhead.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates; union-find nearly constant time per operation [OK]

Hint: Sorting n^2 cells dominates complexity [OK]

Common Mistakes:

• Assuming union-find operations cost O(log n) each
• Confusing brute force simulation complexity with optimal
• Ignoring sorting cost or treating union-find as O(1) without justification

3. Suppose the problem is extended so that variables can be reused multiple times in equations, and inequalities can be chained (e.g., a==b, b!=c, c==a). Which modification to the union-find approach correctly handles early contradiction detection in this scenario?

hard

A. Process all equalities and inequalities in a single pass, unioning and checking contradictions immediately

B. First union all equalities, then check all inequalities for contradictions, returning false if any found

C. Use union-find with early contradiction detection by checking inequalities during union operations and aborting immediately on conflict

D. Replace union-find with a graph coloring approach to handle chained inequalities

Solution

1. Step 1: Understand reuse and chaining impact

   Variables appearing multiple times and chained inequalities require detecting contradictions as soon as they arise to avoid unnecessary work.

2. Step 2: Early contradiction detection

   Checking inequalities during union operations allows immediate detection of conflicts, improving efficiency and correctness.

3. Step 3: Compare alternatives

   Single pass union and check can miss contradictions; two-pass delays detection; graph coloring is more complex and less efficient here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Early contradiction detection aborts on conflict [OK]

Hint: Check contradictions during union to detect conflicts early [OK]

Common Mistakes:

• Checking inequalities only after all unions
• Trying single pass union and check without order

4. Suppose the problem is modified so that each pair can be used multiple times but swaps are only allowed between indices connected by a path of pairs (transitive closure). Which modification to the algorithm is necessary to handle this variant efficiently?

hard

A. Use a brute force DFS to try all swap sequences since union-find no longer applies

B. Use BFS to find shortest swap sequences between indices before swapping

C. Sort the entire string once since any character can be swapped anywhere

D. Use union-find to find connected components, then use a priority queue per component to assign characters on-the-fly

Solution

1. Step 1: Understand transitive closure of pairs

   Indices connected by any path form connected components; union-find efficiently finds these.

2. Step 2: Use priority queues per component

   Priority queues allow on-the-fly assignment of smallest available characters to indices in each component.

3. Step 3: Avoid brute force or BFS over sequences

   Brute force or BFS over swap sequences is inefficient; union-find + priority queue is optimal.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Union-find + priority queue handles multiple swaps and transitive connections efficiently [OK]

Hint: Union-find + priority queue handles transitive swaps efficiently [OK]

Common Mistakes:

• Trying brute force DFS
• Sorting entire string ignoring connectivity
• Using BFS for swap sequences

5. Suppose the Swim in Rising Water problem is modified so that you can revisit cells multiple times (cycles allowed), and the grid elevations can be negative. Which modification to the union-find approach is necessary to correctly solve this variant?

hard

A. Sort cells by absolute elevation and union in that order to handle negative values.

B. Add a visited set to union-find to prevent cycles during union operations.

C. Use a priority queue (min-heap) to process cells by elevation dynamically instead of sorting all upfront.

D. No change needed; the original union-find with sorting by elevation works as is.

Solution

1. Step 1: Understand impact of negative elevations and revisits

   Negative elevations break sorting assumption; revisiting cells means connectivity can change dynamically.

2. Step 2: Identify suitable data structure

   A priority queue allows processing cells in order of elevation dynamically, handling negative values and revisits correctly.

3. Step 3: Why other options fail

   Sorting by absolute elevation loses ordering semantics; visited sets don't apply to union-find; original approach assumes non-negative elevations and no revisits.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Priority queue enables dynamic elevation processing [OK]

Hint: Dynamic processing needed for negative elevations and revisits [OK]

Common Mistakes:

• Sorting by absolute elevation breaks ordering
• Assuming union-find alone handles cycles
• Ignoring negative elevation impact on sorting