algoadvance

Leetcode 547. Number of Provinces

Problem Statement

The problem “Number of Provinces” on LeetCode is defined as follows:

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.

Clarifying Questions

  1. Input Constraints?
    • 1 <= n <= 200
    • isConnected[i][i] = 1 for all i meaning each city is connected to itself.
    • isConnected[i][j] = isConnected[j][i] indicating the undirected nature of the graph.
  2. Output Specification?
    • An integer representing the number of provinces.

Strategy

We need to find the number of connected components in an undirected graph represented by the isConnected matrix. Here’s a straightforward approach:

  1. Graph Representation: Use the isConnected matrix as an adjacency matrix to represent the graph.
  2. Traversal: Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) to find all connected components.
  3. Visited Tracking: Use an array to keep track of visited cities to ensure each city is processed exactly once.
  4. Count Components: Every time we start a new DFS/BFS from an unvisited node, it indicates we’ve found a new province.

Code

Here is the C++ code for the solution using DFS:

#include <vector>
using namespace std;

class Solution {
public:
    void dfs(int city, vector<vector<int>>& isConnected, vector<bool>& visited) {
        visited[city] = true;
        for (int i = 0; i < isConnected.size(); ++i) {
            if (isConnected[city][i] == 1 && !visited[i]) {
                dfs(i, isConnected, visited);
            }
        }
    }

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n = isConnected.size();
        vector<bool> visited(n, false);
        int numberOfProvinces = 0;

        for (int i = 0; i < n; ++i) {
            if (!visited[i]) {
                dfs(i, isConnected, visited);
                numberOfProvinces++;
            }
        }

        return numberOfProvinces;
    }
};

Time Complexity

This solution ensures we efficiently determine the number of provinces in the given graph representation.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI