大师网-带你快速走向大师之路 解决你在学习过程中的疑惑,带你快速进入大师之门。节省时间,提升效率

Leetcode - Number of Connected Components in an Un

思路还是比较清晰的,三种方法

Union Find, BFS, DFS

Union Find采用的方法和找环差不多。统一分类。然后看下最后有几个不同的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,也和找环差不多。顶层对每个结点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