Number of Connected Components in an Undirected Graph

在判断number of connected components in an undirected graph的时候，DFS时不必在意status是0/1/2，也不需要记录parent node，因为我们不care有没有环，只需要用一个boolean的visited数组记录有没有访问过就好了。同理，BFS时也不必在意degree是多少，只要node没有被访问过，就把这个node加到queue里去。

DFS Version

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

        for (int[] e: edges) {
            int v = e[0];
            int u = e[1];
            graph[v].add(u);
            graph[u].add(v);
        }

        boolean[] visited = new boolean[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                sum++;
                dfs(graph, visited, i);
            }
        }

        return sum;
    }

    private void dfs(ArrayList[] graph, boolean[] visited, int current) {
        visited[current] = true;

        for (int i = 0; i < graph[current].size(); i++) {
            int next = (int) graph[current].get(i);
            if (!visited[next]) {
                dfs(graph, visited, next);
            }
        }
    }
}

BFS Version

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

        for (int[] e: edges) {
            int u = e[0];
            int v = e[1];
            graph[u].add(v);
            graph[v].add(u);
        }

        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] visited = new boolean[n];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                sum++;
                queue.offer(i);
                visited[i] = true;
                while (!queue.isEmpty()) {
                    int v = queue.poll();
                    for (int j = 0; j < graph[v].size(); j++) {
                        int u = (int) graph[v].get(j);
                        if (!visited[u]) {
                            queue.offer(u);
                            visited[u] = true;
                        }
                    }
                }
            }
        }

        return sum;
    }
}