Number of Provinces

Problem statement

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.

Example 1:

Input: isConnected = [[1,1,0],[1,1,0],[0,0,1]]Output: 2

Example 2:

Input: isConnected = [[1,0,0],[0,1,0],[0,0,1]]Output: 3

Constraints:

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] is 1 or 0.
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

My solution

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
    const graph = new Map();
    const visited = new Set();
    let count = 0;
    
    for (let i = 0; i < isConnected.length; i++) {
        if (!graph.has(i)) {
            graph.set(i, new Set())
        }
        for (let j = 0; j < isConnected[i].length; j++) {
            if (i !== j && isConnected[i][j] === 1) {
                
                graph.set(i, graph.get(i).add(j))
            }
        }
    }
    
    // console.log(graph)
    
    for (let key of graph.keys()) {
        if (!visited.has(key)) {
            count++
            traverse(graph, key, visited)
        }
    }
    
    // console.log(visited)
    
    return count;
};


function traverse(graph, node, visited) {
    const queue = [node];
    
    while(queue.length) {
        const curr = queue.shift();
        
        visited.add(curr);
        
        // console.log(graph.get(curr))
        
        for (const currNode of graph.get(curr)) {
            if (!visited.has(currNode)) {
                queue.push(currNode)
            }
        }
    }
}