grid47 Exploring patterns and algorithms
Sep 13, 2024
5 min read
Solution to LeetCode 547: Number of Provinces Problem
You are given a matrix where each element indicates if two cities are directly connected. Your task is to determine the number of provinces formed by the cities. A province is a group of directly or indirectly connected cities.
Problem
Approach
Steps
Complexity
Input: The input is an n x n matrix 'isConnected' where 'isConnected[i][j]' is 1 if city 'i' is connected directly to city 'j', and 0 otherwise.
• Explanation: In this example, there are two provinces: one consisting of city 1 and city 2, and the second consisting only of city 3.
Approach: We can solve this problem using either Depth-First Search (DFS) or Union-Find algorithms. Both approaches will allow us to group cities that are connected either directly or indirectly.
Observations:
• We need to find groups of connected cities.
• This can be done by either performing DFS for each unvisited city or by using union-find to group connected cities.
• Using DFS, we can traverse the matrix and mark all connected cities as visited for each unvisited city, which will allow us to count the number of provinces.
Steps:
• Initialize a visited array to track the cities we have already processed.
• For each unvisited city, perform DFS to visit all the cities that are part of the same province.
• Increment the province count each time we start a DFS from an unvisited city.
Empty Inputs:
• The input matrix will always contain at least one city, so there will never be an empty input.
Large Inputs:
• The algorithm should efficiently handle matrices up to 200 x 200 in size.
Special Values:
• If all cities are isolated (no connections), each city forms its own province.
Constraints:
• Ensure the algorithm handles the matrix dimensions efficiently for the upper limit of 200 cities.
intfindCircleNum(vector<vector<int>>& grid) {
int n = grid.size();
UnionFind* uf =new UnionFind(n);
for(int i =0; i < n; i++)
for(int j =0; j < n; j++)
if(grid[i][j] ==1) uf->join(i, j);
return uf->grp;
}
1 : Function Definition
intfindCircleNum(vector<vector<int>>& grid) {
Defines the function `findCircleNum`, which calculates the number of connected components (friend circles) in the given `grid`.
2 : Matrix Size Calculation
int n = grid.size();
Calculates the size of the grid (number of rows/columns) and stores it in variable `n`.
3 : UnionFind Initialization
UnionFind* uf =new UnionFind(n);
Creates a new instance of the `UnionFind` class, initializing it with the grid size `n`. This object will be used to manage the union and find operations for the friend circles.
4 : Outer Loop (Row Traversal)
for(int i =0; i < n; i++)
Starts the outer loop to traverse each row in the grid.
5 : Inner Loop (Column Traversal)
for(int j =0; j < n; j++)
Starts the inner loop to traverse each column in the current row of the grid.
6 : Union Operation
if(grid[i][j] ==1) uf->join(i, j);
Checks if there is a friendship (grid[i][j] == 1). If true, performs a `union` operation to merge the sets of `i` and `j` using the `join` method of the `UnionFind` class.
7 : Return Statement
return uf->grp;
Returns the number of distinct groups (friend circles) found in the grid, which is stored in the `grp` attribute of the `UnionFind` object.
Best Case: O(n^2)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: Since we need to process each entry in the matrix to determine connectivity, the time complexity is O(n^2).
Best Case: O(n)
Worst Case: O(n^2)
Description: The space complexity is O(n) for the visited array, and O(n^2) for storing the matrix.
