SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

The problem is about finding the number of connected components (also called provinces) in a graph represented by an adjacency matrix. Each node in the graph represents a city, and a direct connection between two nodes indicates a direct road between two cities. The goal is to count how many separate provinces (groups of directly or indirectly connected cities) exist in the matrix.

Intuition

The problem can be approached as a graph traversal problem where each province corresponds to a connected component in the graph. By traversing the graph using a depth-first search (DFS) or breadth-first search (BFS), we can explore all nodes (cities) connected to a starting node and mark them as visited. Each time we start a new traversal from an unvisited node, we have identified a new province.

Approach

1. Initialization: We start by initializing a visited array to keep track of which cities have been visited during our traversals.

2. Traversal: For each city, if it has not been visited, we perform a DFS (or BFS) starting from that city to visit all cities that are part of the same province. During this traversal, we mark all connected cities as visited.

3. Counting Provinces: Each time a DFS/BFS is initiated from an unvisited city, it signifies the discovery of a new province, so we increment our province count.

4. Return Result: Finally, the total number of provinces (connected components) is returned as the result.

Complexity

Time Complexity:

The time complexity is (O(n^2)), where (n) is the number of cities (or nodes in the graph). This is because, in the worst case, we may need to visit every city and check every connection between cities.

Space Complexity:

The space complexity is (O(n)) for the visited array and the call stack in the DFS approach. The BFS approach would also use (O(n)) space for the queue.

Code

C++

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int provinces = 0;
        vector<bool> visited(isConnected.size(), false);

        for (int i = 0; i < isConnected.size(); i++) {
            if (!visited[i]) {
                provinces++;
                dfs(isConnected, visited, i);
            }
        }
        return provinces;
    }
private:
    void dfs(const vector<vector<int>>& isConnected, vector<bool>& visited, int i) {
        visited[i] = true;

        for (int j = 0; j < isConnected.size(); j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }
};

Python

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i):
            visited[i] = True
            for j in range(len(isConnected)):
                if isConnected[i][j] == 1 and not visited[j]:
                    dfs(j)

        provinces = 0
        visited = [False] * len(isConnected)

        for i in range(len(isConnected)):
            if not visited[i]:
                provinces += 1
                dfs(i)

        return provinces

Java

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = 0;
        boolean[] visited = new boolean[isConnected.length];

        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                provinces++;
                dfs(isConnected, visited, i);
            }
        }
        return provinces;
    }

    private void dfs(int[][] isConnected, boolean[] visited, int i) {
        visited[i] = true;

        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                dfs(isConnected, visited, j);
            }
        }
    }
}

JavaScript

var findCircleNum = function (isConnected) {

    let provinces = 0;
    let visited = new Array(isConnected.length).fill(false);

    for (let i = 0; i < isConnected.length; i++) {
        if (!visited[i]) {
            provinces++;
            dfs(isConnected, visited, i);
        }
    }
    return provinces;
};

function dfs(isConnected, visited, i) {

    visited[i] = true;
    
    for (let j = 0; j < isConnected.length; j++) {
        if (isConnected[i][j] === 1 && !visited[j]) {
            dfs(isConnected, visited, j);
        }
    }
}