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); } } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter