思路還是比較清晰的埠通，三種方法

Union Find, BFS, DFS

Union Find采用的方法和找環(huán)差不多。統(tǒng)一分類逛犹。然后看下最后有幾個不同的id
My code:

public class Solution {
    private int V = 0;
    private int[] id;
    private int[] sz;
    public int countComponents(int n, int[][] edges) {
        this.V = n;
        id = new int[V];
        sz = new int[V];
        for (int i = 0; i < V; i++) {
            id[i] = i;
            sz[i] = 1;
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            union(u, v);
            union(v, u);
        }
        
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < n; i++) {
            set.add(find(i));
        }
        
        return set.size();
    }
    
    private int find(int u) {
        if (id[u] == u) {
            return u;
        }
        else {
            int ret = find(id[u]);
            id[u] = ret;
            return ret;
        }
    }
    
    private void union(int u, int v) {
        int left = find(u);
        int right = find(v);
        if (left == right) {
            return;
        }
        else {
            if (sz[left] > sz[right]) {
                sz[left] += sz[right];
                id[right] = left;
            }
            else {
                sz[right] += sz[left];
                id[left] = right;
            }
        }
    }
}

DFS端辱，也和找環(huán)差不多。頂層對每個結(jié)點DFS,如果 isVisited[i] 為false虽画，就開始跑 recursion, counter++

My code:

public class Solution {
    private int V = 0;
    private List<List<Integer>> adj;
    
    public int countComponents(int n, int[][] edges) {
        this.V = n;
        adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        int counter = 0;
        boolean[] isVisited = new boolean[V];
        
        for (int i = 0; i < V; i++) {
            if (!isVisited[i]) {
                counter++;
                visit(i, isVisited);
            }
        }
        
        return counter;
    }
    
    private void visit(int u, boolean[] isVisited) {
        isVisited[u] = true;
        for (Integer v : adj.get(u)) {
            if (!isVisited[v]) {
                visit(v, isVisited);
            }
        }
        
    }
}

BFS, 其實也和DFS差不多舞蔽，只不過，具體進去码撰，采用的是BFS遍歷而不是DFS遍歷

My code:

public class Solution {
    private int V = 0;
    private List<List<Integer>> adj;
    
    public int countComponents(int n, int[][] edges) {
        this.V = n;
        adj = new ArrayList<List<Integer>>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<Integer>());
        }
        
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        
        int counter = 0;
        boolean[] isVisited = new boolean[V];
        
        for (int i = 0; i < V; i++) {
            if (!isVisited[i]) {
                counter++;
                visit(i, isVisited);
            }
        }
        
        return counter;
    }
    
    private void visit(int u, boolean[] isVisited) {
        isVisited[u] = true;
        for (Integer v : adj.get(u)) {
            if (!isVisited[v]) {
                visit(v, isVisited);
            }
        }
        
    }
}

圖的簡單中等題就差不多這樣了渗柿。

Anyway, Good luck, Richardo! -- 09/10/2016