Number of Provinces

Problem Description

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise. Return the total number of provinces.

Key Insights

• The problem can be represented as a graph where cities are nodes and connections are edges.
• A province corresponds to a connected component in the graph.
• Depth-First Search (DFS) or Breadth-First Search (BFS) can be used to explore and count connected components.
• The input matrix is symmetric and diagonal, indicating undirected connections.

Space and Time Complexity

Time Complexity: O(n^2) - We potentially visit every element in the adjacency matrix.

Space Complexity: O(n) - We may use an auxiliary data structure (like a visited array) proportional to the number of cities.

Solution

To solve the problem, we can use Depth-First Search (DFS) or Breadth-First Search (BFS) to explore the graph. Each time we start a new DFS/BFS from an unvisited node, we discover a new province. We will mark nodes as visited to avoid counting them again.

1. Iterate through each city.
2. For each unvisited city, perform a DFS/BFS to visit all directly or indirectly connected cities.
3. Count each initiation of DFS/BFS as a new province.

The adjacency matrix isConnected will help us determine direct connections between the cities.

Code Solutions