Simple Java DFS O(N)


  • 0
    I

    This approach is similar to simply DFS. Total runtime worst runtime complexity is O(N) (best case each component consists of 1 node, worst case is there is 1 component.

    1. Generate HashMap to access edges in O(1) time
    2. Created array of flags whether each node is visited
    3. Use simply DFS to mark all connected nodes as marked and increment result, if current starting node is not visited yet

    Runtime Complexity: O(N)
    Space Complexity: O(N^2) (worst case: every node is connected to every other node), it can be avoided by reusing input edges, but then runtime will be O(N * K), where K is number of edges.

    public class Solution {
        public int countComponents(int n, int[][] edges) {
            //generate map to constant acces of edges outgoing from point
            HashMap<Integer, List<Integer>> map =  new HashMap<Integer, List<Integer>>();
            for(int[] a : edges) {
                if(!map.containsKey(a[0])) {
                    map.put(a[0], new ArrayList<Integer>());
                }
                if(!map.containsKey(a[1])) {
                    map.put(a[1], new ArrayList<Integer>());
                }
                
                //bidirectional
                map.get(a[0]).add(a[1]);
                map.get(a[1]).add(a[0]);
            }
            
            boolean[] visited = new boolean[n];
            int res = 0;
            for(int i = 0; i < n; i++) {
                if(!visited[i]) {
                    greedy(map, i, visited);
                    res++;
                }
            }
            
            return res;
        }
        
        void greedy(HashMap<Integer, List<Integer>> map, int source, boolean[] visited) {
            if(visited[source]) {
                return;
            }
            
            visited[source] = true;
            //no connections
            if(!map.containsKey(source)) {
                return;
            }
            for(int a : map.get(source)) {
                greedy(map, a, visited);
            }
        }
    }
    

Log in to reply
 

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