Concise Java DFS solution


  • 0
    W
    public class Solution {
    public int countComponents(int n, int[][] edges) {
        
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<Integer>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            graph.get(edges[i][0]).add(edges[i][1]);
            graph.get(edges[i][1]).add(edges[i][0]);
        }
        
        boolean[] visit = new boolean[n];
        Arrays.fill(visit, false);
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                bfs(i, graph, visit);
                count++;
            }
        }
        return count;
    }
    private void bfs(int i, Map<Integer, List<Integer>> graph, boolean[] visit) {
        if (visit[i]) {
            return;
        }
        visit[i] = true;
        List<Integer> neighbors = graph.get(i);
        for (Integer integer: neighbors) {
            bfs((int)integer, graph, visit);
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.