算法1

(BFS) $O(n)$

class Solution {
    public boolean validTree(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        List<Set<Integer>> adjList = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        for(int[] edge : edges) {
            int first = edge[0];
            int second = edge[1];
            adjList.get(first).add(second);
            adjList.get(second).add(first);
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        //bfs
        while(!queue.isEmpty()) {
            int cur = queue.poll();
            if(visited[cur]) return false;

            visited[cur] = true;

            for(int next : adjList.get(cur)) {
                adjList.get(next).remove(cur); //边处理边删掉，去掉邻接表力重复掉边
                queue.offer(next);
            }
        }

        boolean res = true;
        for(boolean val : visited) res &= val;
        return res;
    }
}

时间复杂度

O(n)

参考文献

C++ 代码

blablabla

算法2

(DFS) $O(n)$

时间复杂度

参考文献

class Solution {
    public boolean validTree(int n, int[][] edges) {
        boolean[] visited = new boolean[n];
        List<Set<Integer>> adjList = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }

        for(int[] edge : edges) {
            int first = edge[0];
            int second = edge[1];
            adjList.get(first).add(second);
            adjList.get(second).add(first);
        }

        //DFS
        if(hasCycle(0, -1, visited, adjList)) return false;

        boolean res = true;
        for(boolean val : visited) res &= val;
        return res;
    }

    private boolean hasCycle(int node, int parent, boolean[] visited, List<Set<Integer>> adjList) {
        visited[node] = true;
        for(int next : adjList.get(node)) {
            if (next == parent) continue;
            if (visited[next]) return true;
            else if(hasCycle(next, node, visited, adjList)) return true;

        }
        return false;
    }
}

算法3

(Union find) $O(n)$

class Solution {
    int[] f;
    int count;
    public boolean validTree(int n, int[][] edges) {
        f = new int[n];
        count = 0;
        for(int i = 0; i < n; i++) {
            f[i] = i;
        }

        for(int[] edge : edges) {
            int x = edge[0];
            int y = edge[1];
            if(find(x) == find(y)) return false;
            union(x, y);
        }
        return (count == n-1);
    }

    private int find(int x) {
        if (f[x] != x) {
            f[x] = find(f[x]);
        }
        return f[x];
    }

    private void union(int x, int y) {
        if(f[x] != f[y]) {
            f[find(x)] = f[y];
        }
        count++;
    }
}

时间复杂度

参考文献

• Edege case: edges.length != n - 1说明有孤立点

邻接表：用set存adjList，方便删改

Union find 的两个要点：
find()里面f[x] != x, f[x] = find(f[x])
union里面f[x] != f[y], f[find(x)] = f[y]

BFS: 时间复杂度O(n), 空间复杂度O(n)
DFS: 时间复杂度O(n), 空间复杂度O(n)
Union Find: 时间复杂度O(n), 空间复杂度O(n)