Java Union find & DFS & BFS Code (very clean)


  • 20
    B
    public class Solution {
        
        public int countComponents(int n, int[][] edges) {
            if (n <= 1) {
                return n;
            }
            int[] roots = new int[n];
            for (int i = 0; i < n; i++) {
                roots[i] = i;
            }
            for (int[] edge : edges) {
                int x = find(roots, edge[0]);
                int y = find(roots, edge[1]);
                if (x != y) {
                    roots[x] = y;
                    n--;
                }
            }
            
            return n;
        }
        
        public int find(int[] roots, int id) {
            int x = id;
            while (roots[id] != id) {
                id = roots[id];
            }
            while (roots[x] != id) {
                int fa = roots[x];
                roots[x] = id;
                x = fa;
            }
            
            return id;
        }
    }
    

    DFS:

    public class Solution {
        
        public int countComponents(int n, int[][] edges) {
            if (n <= 1) {
                return n;
            }
            List<List<Integer>> adjList = new ArrayList<List<Integer>>();
            for (int i = 0; i < n; i++) {
                adjList.add(new ArrayList<Integer>());
            }
            for (int[] edge : edges) {
                adjList.get(edge[0]).add(edge[1]);
                adjList.get(edge[1]).add(edge[0]);
            }
            boolean[] visited = new boolean[n];
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    count++;
                    dfs(visited, i, adjList);
                }
            }
            
            return count;
        }
        
        public void dfs(boolean[] visited, int index, List<List<Integer>> adjList) {
            visited[index] = true;
            for (int i : adjList.get(index)) {
                if (!visited[i]) {
                    dfs(visited, i, adjList);
                }
            }
        }
    }
    

    BFS:

    public class Solution {
        
        public int countComponents(int n, int[][] edges) {
            if (n <= 1) {
                return n;
            }
            List<List<Integer>> adjList = new ArrayList<List<Integer>>();
            for (int i = 0; i < n; i++) {
                adjList.add(new ArrayList<Integer>());
            }
            for (int[] edge : edges) {
                adjList.get(edge[0]).add(edge[1]);
                adjList.get(edge[1]).add(edge[0]);
            }
            boolean[] visited = new boolean[n];
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (!visited[i]) {
                    count++;
                    Queue<Integer> queue = new LinkedList<Integer>();
                    queue.offer(i);
                    while (!queue.isEmpty()) {
                        int index = queue.poll();
                        visited[index] = true;
                        for (int next : adjList.get(index)) {
                            if (!visited[next]) {
                                queue.offer(next);
                            }
                        }
                    }
                }
            }
            
            return count;
        }
    }

  • 7
    E

    One suggestion to your code (BFS): mark the node as visited when you add it to the queue, not when it's popped. Otherwise you might add nodes multiple times to the queue. The result will still be OK but it's unnecessary computation.


  • 0
    S
    public static int countComponents(int n, int[][] edges) {
    	boolean[] visited = new boolean[n];
    	int numConnectedEdges = 0;
    	for (int i = 0 ; i< edges.length; i++) {
    		int[] edge = edges[i];
            // if we are visiting both vertices for first time
    		if (!visited[edge[0]] && !visited[edge[1]]) {
    			++numConnectedEdges;
    		}
    		visited[edge[0]] = true;
    		visited[edge[1]] = true;
    	}
        // count the vertices which doesnot have edges
    	for (int i = 0 ; i< visited.length; i++) {
    		if (!visited[i]) {
    			++numConnectedEdges;
    		}
    	}
    	return numConnectedEdges;
    }

  • 0
    A
    This post is deleted!

  • 0
    C

    I think there is no node will be added to the queue multiple times (BFS solution). I also doubt whether marking the node as visited when you add it into the queue is right since you have to mark the original node too.


  • 1
    E

    I suppose you can use a queue that also has the set property but that again may add extra unnecessary computation, as checking for identical items at insert time is more expensive than to... not check.
    Adding the original node really shouldn't be a problem. You just mark it as visited before going into BFS


  • 0

    @syamksundar not AC dude.


Log in to reply
 

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