Leetcode #323. Number of Connected Components in an Undirected Graph

[yokostan]

Union Find, runtime beats 66%:

class Solution {
    public int countComponents(int n, int[][] edges) {
        int[] roots = new int[n];
        for (int i = 0; i < n; i++) {
            roots[i] = i;
        }

        for (int i = 0; i < edges.length; i++) {
            int root1 = find(roots, edges[i][0]);
            int root2 = find(roots, edges[i][1]);
            if (root1 != root2) {
                roots[root1] = root2;
                n--;
            }
        }

        return n;
    }

    public int find(int[] roots, int root) {
        if (roots[root] == root) return root;
        else return find(roots, roots[root]);
    }
}

DFS beats 55%:

class Solution {
    public int countComponents(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        int res = 0;
        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]);
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            dfs(i, visited, adjList);
            res++;
        }

        return res;
    }

    private void dfs(int idx, boolean[] visited, List<List<Integer>> adjList) {
        visited[idx] = true;
        for (int i : adjList.get(idx)) {
            if (visited[i]) continue;
            dfs(i, visited, adjList);
        }
    }
}

BFS, beats 32%:

class Solution {
    public int countComponents(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        int res = 0;
        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]);
        }

        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            res++;
            Queue<Integer> queue = new LinkedList<Integer>();
            queue.offer(i);
            while (!queue.isEmpty()) {
                int idx = queue.poll();
                visited[idx] = true;
                for (int next : adjList.get(idx)) {
                    if (!visited[next]) {
                        queue.offer(next);
                    }
                }
            }
        }

        return res;
    }
}