Number of Connected Components in an Undirected Graph

lc 323

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

time complexity: o(e+v)

BFS method:

class Node {
    int val;
    List<Node> neighbors;
    public Node(int i){
        this.val = i;
        neighbors = new ArrayList<>();
    }

}

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if ( n == 0 ) return 0;
        if ( edges == null || edges.length == 0 || edges[0] == null || edges[0].length == 0) return n;
        List<Node> graph = new ArrayList<Node>();
        for ( int i = 0 ; i < n; i++ ){
            graph.add(new Node(i));
        }

        for (int[] edge : edges) {
            graph.get(edge[0]).neighbors.add(graph.get(edge[1]));
            graph.get(edge[1]).neighbors.add(graph.get(edge[0]));
        }

        boolean[] visit = new boolean[n];
        int count = 0;
        for ( Node cur : graph){
            if (visit[cur.val] ) continue;
            count++;
            bfs(visit, cur);
        }

        return count;

    }

    public void bfs(boolean[] visit, Node cur){
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(cur);
        visit[cur.val] = true;
        while ( ! queue.isEmpty()){
            int size = queue.size();
            for ( int i = 0 ; i < size; i++ ){
                Node c = queue.poll();
                for (Node n : c.neighbors){
                    if (visit[n.val]) continue;
                    queue.offer(n);
                    visit[n.val] = true;
                }
            }
        }

    }
}

Union find method time complexity: union find o(1) amortized analysis

class Solution {
    class UnionFind {
        Map<Integer, Integer> fathers;
        int count;
        public UnionFind(int n) {
            fathers = new HashMap<>();
            for (int i = 0; i < n; i++) {
                fathers.put(i, i);
            }
            count = n;
        }

        public int compressedFind(int i) {
            int father = i;
            while (fathers.get(father) != father) {
                father = fathers.get(father);
            }
            while (fathers.get(i) != i) {
                fathers.put(i, father);
                i = fathers.get(father);
            }
            return father;
        }

        public void union(int a, int b) {
            int aFather = compressedFind(a);
            int bFather = compressedFind(b);
            if (aFather != bFather) {
                fathers.put(aFather, bFather);
                count--;
            }
        }
    }

    public int countComponents(int n, int[][] edges) {
        UnionFind u = new UnionFind(n);
        //int res = n;
        for (int i = 0; i < edges.length; i++) {
            u.union(edges[i][0], edges[i][1]);
        }
        return u.count;
    }
}