Q5 Number of Provinces - LeetCode 547
Sat Apr 08 2023 16:27:18 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
class Solution {
public int findCircleNum(int[][] isConnected) {
/* convert this question to graph components */
//making graph using input
HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();
int n = isConnected.length; //nxn matrix
for(int i = 0 ; i < n ;i++){
for(int j = 0 ; j < n ; j++){
//storing edges between nodes
if(isConnected[i][j] == 1){
graph.computeIfAbsent(i , k -> new ArrayList<>()).add(j);
graph.computeIfAbsent(j , k -> new ArrayList<>()).add(i);
}
}
}
boolean visited[] = new boolean[n];
int component = 0;
//looping through every node and firing dfs
for(int i = 0 ; i < n ; i++){
if(visited[i] == false){
dfs(graph , i , visited);
component++;
}
}
return component;
}
public void dfs (HashMap<Integer,ArrayList<Integer>> graph , int source ,
boolean[] visited){
visited[source] = true;
for(int edge : graph.get(source)){
if(visited[edge] == false)
dfs(graph , edge , visited);
}
}
}
content_copyCOPY
https://leetcode.com/problems/number-of-provinces/
Comments