547. Number of Provinces

MediumDepth-First SearchBreadth-First SearchUnion FindGraph
Leetcode Link

Problem Description

In this problem, we are given a total of n cities and a matrix called isConnected which is an n x n matrix. The element isConnected[i][j] will be 1 if there is a direct connection between city i and city j, and 0 if there is no direct connection. A set of cities is considered a province if all cities within the set are directly or indirectly connected to each other, and no city outside of the set is connected to any city within the set.

Our task is to determine how many provinces there are given the isConnected matrix.

Intuition

To find the solution, we conceptualize the cities and the connections between them as a graph, where each city is a node and each direct connection is an edge. Now, the problem translates to finding the number of connected components in the graph. Each connected component will represent one province.

To do this, we use Depth-First Search (DFS). Here's the intuition behind using DFS:

  1. We start with the first city and perform a DFS to mark all cities that are connected directly or indirectly to it. These cities form one province.
  2. Once the DFS is completed, we look for the next city that hasn't been visited yet and perform a DFS from that city to find another province.
  3. We repeat this process until all cities have been visited.

Each time we initiate a DFS from a new unvisited city, we know that we've found a new province, so we increment our province count. The DFS ensures that we navigate through all the cities within a province before moving on to the next one.

By doing the above steps using a vis (visited) list to keep track of which cities have been visited, we can effectively determine and count all the provinces.

Learn more about Depth-First Search, Breadth-First Search, Union Find and Graph patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of these pictures shows the visit order of a depth-first search?

Solution Approach

The solution uses a Depth-First Search (DFS) algorithm to explore the graph formed by the cities and connections. It utilizes an array vis to keep track of visited nodes (cities) to ensure we don't count the same province multiple times. Below is a step-by-step walk-through of the implementation:

  1. Define a recursive function dfs(i: int) that will perform a depth-first search starting from city i.
  2. Inside the dfs function, mark the current city i as visited by setting vis[i] to True.
  3. Iterate over all cities using j (which correspond to the columns of isConnected[i]).
  4. For each city j, check if j has not been visited (not vis[j]) and is directly connected to i (isConnected[i][j] == 1).
  5. If that's the case, call dfs(j) to visit all cities connected to j, marking the entire connected component as visited.

The solution then follows these steps using the vis list:

  1. Initialize the vis list to be of the same length as the number of cities (n), with all elements set to False, indicating that no cities have been visited yet.
  2. Initialize a counter ans to 0, which will hold the number of provinces found.
  3. Iterate through all cities i from 0 to n - 1.
  4. For each city i, check if it has not been visited yet (not vis[i]).
  5. If it hasn't, it means we've encountered a new province. Call dfs(i) to mark all cities within this new province as visited.
  6. Increment the ans counter by 1 as we have found a new province.
  7. Continue the loop until all cities have been visited and all provinces have been counted.

At the end of the loop, ans will contain the total number of provinces, which the function returns. This completes the solution implementation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider there are 4 cities, and the isConnected matrix is as follows:

1isConnected = [
2    [1, 1, 0, 0],
3    [1, 1, 0, 0],
4    [0, 0, 1, 1],
5    [0, 0, 1, 1]
6]

Here, cities 0 and 1 are connected, as well as cities 2 and 3, forming two distinct provinces.

We initialize our vis list as [False, False, False, False] and set our province counter ans to 0.

Now let's perform the steps of the algorithm:

  1. We start with city 0 and run dfs(0).

    • In dfs(0), city 0 is marked visited: vis = [True, False, False, False].
    • We find that city 0 is connected to city 1, dfs(1) is called.
      • In dfs(1), city 1 is marked visited: vis = [True, True, False, False].
      • There are no unvisited cities connected to city 1, so dfs(1) ends.

  2. Since all cities connected to city 0 are now visited, dfs(0) ends. We've found our first province, so we increment ans to 1.

  3. Next, we move to city 1, but since it's already visited, we proceed to city 2 and run dfs(2).

    • In dfs(2), city 2 is marked visited: vis = [True, True, True, False].
    • We find that city 2 is connected to city 3, dfs(3) is called.
      • In dfs(3), city 3 is marked visited: vis = [True, True, True, True].
      • There are no unvisited cities connected to city 3, so dfs(3) ends.

  4. At this point, all cities connected to city 2 are visited, ending dfs(2). We've found another province, incrementing ans to 2.

  5. Finally, we move to city 3 and see it's already visited.

Now, we've visited all cities, and there are no unvisited cities to start a new dfs from. Thus, we conclude there are 2 provinces in total, which is the value of ans.

The full algorithm will perform similarly on a larger scale, incrementing the province count each time it initiates a DFS on an unvisited city, and continuing until all cities are visited. The final result is the total number of provinces.

Solution Implementation

1from typing import List
2
3class Solution:
4    def findCircleNum(self, isConnected: List[List[int]]) -> int:
5        # Depth-First Search function which marks the nodes as visited
6        def dfs(current_city: int):
7            visited[current_city] = True  # Mark the current city as visited
8            for adjacent_city, connected in enumerate(isConnected[current_city]):
9                # If the adjacent city is not visited and there is a connection,
10                # then continue the search from that city
11                if not visited[adjacent_city] and connected:
12                    dfs(adjacent_city)
13
14        # Number of cities in the given matrix
15        num_cities = len(isConnected)
16        # Initialize a visited list to keep track of cities that have been visited
17        visited = [False] * num_cities
18        # Counter for the number of provinces (disconnected components)
19        province_count = 0
20        # Loop over each city and perform DFS if it hasn't been visited
21        for city in range(num_cities):
22            if not visited[city]:  # If the city hasn't been visited yet
23                dfs(city)  # Start DFS from this city
24                # After finishing DFS, we have found a new province
25                province_count += 1
26        # Return the total number of disconnected components (provinces) in the graph
27        return province_count
28
1class Solution {
2    // This variable stores the connection graph.
3    private int[][] connectionGraph;
4    // This array keeps track of visited cities to avoid repetitive checking.
5    private boolean[] visited;
6
7    // The method finds the number of connected components (provinces or circles) in the graph.
8    public int findCircleNum(int[][] isConnected) {
9        // Initialize the connection graph with the input isConnected matrix.
10        connectionGraph = isConnected;
11        // The number of cities is determined by the length of the graph.
12        int numCities = connectionGraph.length;
13        // Initialize the visited array for all cities, defaulted to false.
14        visited = new boolean[numCities];
15        // Initialize the count of provinces to zero.
16        int numProvinces = 0;
17        // Iterate over each city.
18        for (int i = 0; i < numCities; ++i) {
19            // If the city is not yet visited, it's a new province.
20            if (!visited[i]) {
21                // Perform a depth-first search starting from this city.
22                dfs(i);
23                // Increment the number of provinces upon returning from DFS.
24                ++numProvinces;
25            }
26        }
27        // Return the total number of provinces found.
28        return numProvinces;
29    }
30
31    // Depth-first search recursive method that checks connectivity.
32    private void dfs(int cityIndex) {
33        // Mark the current city as visited.
34        visited[cityIndex] = true;
35        // Iterate over all possible destinations from the current city.
36        for (int destination = 0; destination < connectionGraph.length; ++destination) {
37            // If the destination city is not yet visited and is connected to the current city,
38            // perform a DFS on it.
39            if (!visited[destination] && connectionGraph[cityIndex][destination] == 1) {
40                dfs(destination);
41            }
42        }
43    }
44}
45
1#include <vector>
2#include <cstring>
3#include <functional>
4
5class Solution {
6public:
7    int findCircleNum(std::vector<std::vector<int>>& isConnected) {
8        // Get the number of cities (nodes).
9        int cities = isConnected.size();
10      
11        // Initialize the count of provinces (initially no connection is found).
12        int provinceCount = 0;
13      
14        // Visited array to keep track of the visited cities.
15        bool visited[cities];
16      
17        // Initialize all cities as unvisited.
18        std::memset(visited, false, sizeof(visited));
19      
20        // Define depth-first search (DFS) as a lambda function.
21        std::function<void(int)> dfs = [&](int cityIndex) {
22            // Mark the current city as visited.
23            visited[cityIndex] = true;
24          
25            // Visit all the cities connected to the current city.
26            for (int j = 0; j < cities; ++j) {
27                // If the city is not visited and is connected, perform DFS on it.
28                if (!visited[j] && isConnected[cityIndex][j]) {
29                    dfs(j);
30                }
31            }
32        };
33      
34        // Iterate over each city to count the number of provinces.
35        for (int i = 0; i < cities; ++i) {
36            // If the city is not yet visited, it is part of a new province.
37            if (!visited[i]) {
38                dfs(i); // Perform DFS to visit all cities in the current province.
39                ++provinceCount; // Increment the count of provinces.
40            }
41        }
42      
43        // Return the total number of provinces found.
44        return provinceCount;
45    }
46};
47
1// Function to find the number of connected components (circles of friends) in the graph
2function findCircleNum(isConnected: number[][]): number {
3    // Total number of nodes in the graph
4    const nodeCount = isConnected.length;
5    // Array to track visited nodes during DFS traversal
6    const visited: boolean[] = new Array(nodeCount).fill(false);
7
8    // Depth-First Search (DFS) function to traverse the graph
9    const depthFirstSearch = (node: number) => {
10        // Mark current node as visited
11        visited[node] = true;
12        for (let adjacentNode = 0; adjacentNode < nodeCount; ++adjacentNode) {
13            // For each unvisited adjacent node, perform DFS traversal
14            if (!visited[adjacentNode] && isConnected[node][adjacentNode]) {
15                depthFirstSearch(adjacentNode);
16            }
17        }
18    };
19
20    // Counter to keep track of the number of connected components (circles)
21    let circleCount = 0;
22
23    // Loop through all nodes
24    for (let node = 0; node < nodeCount; ++node) {
25        // If the node hasn't been visited, it's the start of a new circle
26        if (!visited[node]) {
27            depthFirstSearch(node); // Perform DFS from this node
28            circleCount++; // Increment the number of circles
29        }
30    }
31
32    // Return the total number of circles found
33    return circleCount;
34}
35
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The given code snippet represents the Depth-First Search (DFS) approach for finding the number of connected components (which can be referred to as 'circles') in an undirected graph represented by an adjacency matrix isConnected.

Time Complexity

The time complexity of the algorithm is O(N^2), where N is the number of vertices (or cities) in the graph. This complexity arises because the algorithm involves visiting every vertex once and, for each vertex, iterating through all possible adjacent vertices to explore the edges. In the worst-case scenario, this results in checking every entry in the isConnected matrix once, which has N^2 entries.

The dfs function explores all connected vertices through recursive calls. Since each edge and vertex will only be visited once in the DFS traversal, the total number of operations performed will be related to the total number of vertices and edges. However, because the graph is represented by an N x N adjacency matrix and it must be fully inspected to discover all connections, the time is bounded by the size of the matrix (N^2).

Space Complexity

The space complexity of the algorithm is O(N), which comes from the following:

  1. The recursion stack for DFS, which in the worst case, could store up to N frames if the graph is implemented as a linked structure such as a list of nodes (a path with all nodes connected end-to-end).
  2. The vis visited array, which is a boolean array of length N used to track whether each vertex has been visited or not to prevent cycles during the DFS.

Given that N recursion calls could happen in a singly connected component spanning all the vertices, the space taken by the call stack should be considered in the final space complexity, merging it with the space taken by the array to O(N).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ