261. Graph Valid Tree

三刷 05/2022

Version #5 DFS with Stack

Time O(N)

Space O(N)

Runtime: 4 ms, faster than 49.96% of Java online submissions for Graph Valid Tree.

Memory Usage: 47.1 MB, less than 35.44% of Java online submissions for Graph Valid Tree.

class Solution {

    public boolean validTree(int n, int[][] edges) {

        if (edges == null || edges.length != n - 1) {

            return false;

        }

        List<Integer>[] graph = new ArrayList[n];

        for (int i = 0; i < n; i++) {

            graph[i] = new ArrayList<>();

        }

        for (int[] edge : edges) {

            graph[edge[0]].add(edge[1]);

            graph[edge[1]].add(edge[0]);

        }

        Stack<Integer> stack = new Stack<>();

        Set<Integer> visited = new HashSet<>();

        stack.push(0);

        visited.add(0);

        while (!stack.isEmpty()) {

            Integer curr = stack.pop();

            for (Integer next : graph[curr]) {

                if (visited.contains(next)) {

                    continue;

                }

                stack.push(next);

                visited.add(next);

            }

        }

        return visited.size() == n;

    }

}

Version #1 Union Find
[2ND TRY]
71.21 %
class Solution {
    class UF {
private int[] id;
private int[] size;
private int count;
public UF(int N) {
id = new int[N];
size = new int[N];
count = N;
for (int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}

private int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}

// True if p q are not already connected
public boolean union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if (rootP == rootQ) {
return false;
}
this.count--;
if (size[rootP] < size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
return true;
}

public int getCount() {
return this.count;
}
}


public boolean validTree(int n, int[][] edges) {
UF uf = new UF(n);
for (int[] edge : edges) {
if (!uf.union(edge[0], edge[1])) {
return false;
}
}
return uf.getCount() == 1;
  }
}


[1ST TRY]
97.86%

public class Solution {
    private int[] father;
    public boolean validTree(int n, int[][] edges) {
        if (n <= 0 || edges == null) return false;
        if (n - 1 != edges.length) return false;
        //All n nodes are pointing to itself
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        for (int[] edge : edges) {
            if (!union(edge[0], edge[1])) return false;
        }
     
     
        return true;
    }
    private int find(int x) {
        if (father[x] == x) return x;
        father[x] = find(father[x]);
        return father[x];
    }
 
    private boolean union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA == rootB) return false;
        else {
            father[rootA] = rootB;
            return true;
        }
    }
}


Version #2 DFS
24.78 %
class Solution {
    public boolean validTree(int n, int[][] edges) {
// Connected undirected graph with only one connected component and without any cycle
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
Set<Integer> visited = new HashSet<>();
return dfs(graph, 0, -1, visited) && visited.size() == n;
  }
 
  private boolean dfs(List<List<Integer>> graph, int curr, int parent, Set<Integer> visited) {
List<Integer> neighbors = graph.get(curr);
        visited.add(curr);
for (Integer neighbor : neighbors) {
if (neighbor != parent) {
if (visited.contains(neighbor)) {
return false;
}
if (!dfs(graph, neighbor, curr, visited)) {
return false;
}
}
}
return true;
}
}


57.39%
public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n <= 0 || edges == null) return false;
        if (n - 1 != edges.length) return false;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        if (noCycle(0, -1, graph, visited) == false) return false;
        for (boolean b : visited) {
            if (b == false) return false;
        }
        return true;
    }
    private boolean noCycle(int node, int prev, List<List<Integer>> graph, boolean[] visited) {
        List<Integer> neighbors = graph.get(node);
        visited[node] = true;
        for (Integer neighbor : neighbors) {
            if (neighbor == prev) continue;
            if (visited[neighbor]) return false;
            if (!noCycle(neighbor, node, graph, visited)) return false;
        }
        return true;
    }
}

Version #3 BFS
在保证了n - 1 == edges.length的情况下
如果有环，就会有不能被visit的点
52.96% 
public class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (n <= 0 || edges == null) return false;
        if (n - 1 != edges.length) return false;
     
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<Integer>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        Queue<Integer> que = new LinkedList<>();
        que.add(0);
        boolean[] visited = new boolean[n];
        int curr = 0;
        List<Integer> neighbors = null;
        while (!que.isEmpty()) {
            curr = que.poll();
            visited[curr] = true;
            neighbors = graph.get(curr);
            for (Integer neighbor : neighbors) {
                if(visited[neighbor]) continue;
                que.offer(neighbor);
            }
        }
        for (boolean b : visited) {
            if (!b) return false;
        }
        return true;
    }
}



Version #4 BFS - Check valid by counting visited nodes
public class Solution {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        // Write your code here
        //System.out.println("start");
        if (n == 0) {
            return false;
        }
        if (edges.length != n - 1) {
            return false;
        }
     
     
        ArrayList<HashSet<Integer>> graph = buildGraph(n, edges);
        Queue<Integer> que = new LinkedList<>();
     
        Set<Integer> hash = new HashSet<Integer>();
        int visited = 0;
        que.offer(0);
        hash.add(0);
        //System.out.println("regular case");
     
        //***************************************
        //check visited before the node is pushed
        //add to visited count when the node is polled out
        while(!que.isEmpty()) {
            int node = que.poll();
            visited ++;
            //System.out.println("visited: " + visited + " node: " + node);
            Set<Integer> neighbors = graph.get(node);
            for (int neighbor : neighbors) {
                //System.out.println("neighbor: " + neighbor);
                if (hash.contains(neighbor)) {
                    continue;
                } else {
                    hash.add(neighbor);
                    que.offer(neighbor);
                }
            }
        }
        //System.out.println(visited);
        return visited == n;
     
    }
    public ArrayList<HashSet<Integer>> buildGraph(int n, int[][] edges) {
        ArrayList<HashSet<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new HashSet<Integer>());
        }
        for (int[] edge: edges) {
            int e0 = edge[0];
            int e1 = edge[1];
            graph.get(e0).add(e1);
            graph.get(e1).add(e0);
        }
        return graph;
    }
}