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.

&nbsp;
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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 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]


class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        graph = defaultdict(list)
        for i,x in enumerate(isConnected):
            for j,n in enumerate(x):
                if j!=i and n == 1:
                    graph[i].append(j)
            
        visit = set()
        
        def dfs(node):
            if node not in graph:
                return 
            for neighbor in graph[node]:
                if neighbor not in visit:
                    visit.add(neighbor)
                    dfs(neighbor)
        count = 0
        for i in range(len(isConnected)):
            if i in visit:
                continue
            count+=1
            dfs(i)
        return count
class Solution {
    public int findCircleNum(int[][] isConnected) {
        int size = isConnected.length;
        boolean[] isCheck = new boolean[size+1];
        int ans = 0;

        for(int i=1; i<=size; i++){

            if(!isCheck[i]){ // Doing BFS if it's false in isCheck[]
                Queue<Integer> q = new LinkedList<>();
                q.add(i);
                ans++; // No. of queue = No. of Graphs

                while(!q.isEmpty()){
                    int temp = q.remove();
                    isCheck[temp] = true;

                    for(int j=0; j<size; j++){
                        if(isConnected[temp-1][j]==1 && !isCheck[j+1])
                            q.add(j+1);
                    }
                }
            }
        }
        return ans;
    }
}
class Solution {
private:
    void dfs(int node,vector<vector<int>> &graph,int n,vector<bool> &vis){

        vis[node] = true;

        for(int j = 0; j < graph[node].size(); j++){
            if(graph[node][j] == 1 and !vis[j]){
                dfs(j,graph,n,vis);
            }
        }

    }
public:
    int findCircleNum(vector<vector<int>>& isConnected) {

        int n = isConnected.size();

        vector<bool> vis(n,false);

        int ans = 0;

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

        return ans;

    }
};
function DisjointSet (size) {
    this.root = []
    this.rank = []
    this.size = size
    for (let i = 0; i < size; i++) {
        this.root.push(i)
        this.rank.push(1)
    }
    this.find = function(x) {
        if (x === this.root[x]) {
            return x
        }
        this.root[x] = this.find(this.root[x])
        return this.root[x]
    }
    this.union = function(x, y) {
        const rootX = this.find(x)
        const rootY = this.find(y)
        if (rootX === rootY) return
        this.size--
        if (this.rank[rootX] > this.rank[rootY]) {
            this.root[rootY] = this.root[rootX]
        }
        else if (this.rank[rootX] < this.rank[rootY]) {
            this.root[rootX] = this.root[rootY]
        }
        else {
            this.root[rootY] = this.root[rootX]
            this.rank[rootX]++
        }
    }
}

/**
 * @param {number[][]} isConnected
 * @return {number}
 */
var findCircleNum = function(isConnected) {
    const n = isConnected.length
    const disjointSet = new DisjointSet(isConnected.length)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (isConnected[i][j]) {
                disjointSet.union(i, j)
            }
        }
    }
    return disjointSet.size
};
Number of Provinces