Graph Valid Tree

Givennnodes labeled from0ton - 1and a list ofundirectededges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

Notice

You can assume that no duplicate edges will appear in edges. Since all edges areundirected,[0, 1]is the same as[1, 0]and thus will not appear together in edges.

Example

Givenn = 5andedges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Givenn = 5andedges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Solution 1: DFS.

public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
    HashSet<Integer> visited = new HashSet<Integer>();
    buildGraph(n, edges, graph);
    if(!dfs(0, -1, graph, n, visited)) {
        return false;
    }
    if(visited.size() != n) {
        return false;
    }
    return true;
}
public void buildGraph(int n, int[][] edges, HashMap<Integer, ArrayList<Integer>> graph) {
    for(int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<Integer>());
    }
    for(int i = 0; i < edges.length; i++) {
        graph.get(edges[i][0]).add(edges[i][1]);
        graph.get(edges[i][1]).add(edges[i][0]);
    }
}
public boolean dfs(int node, int parent, HashMap<Integer, ArrayList<Integer>> graph, int n, HashSet<Integer> set) {
    if(set.contains(node)) {
        return false;
    }
    set.add(node);    
    for(Integer i : graph.get(node)) {
        if(i != parent && !dfs(i, node, graph, n, set)) {
            return false;
        }
    }
    return true;
}

Solution 2: BFS.

public boolean validTree(int n, int[][] edges) {
    HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>();
    buildGraph(n, edges, graph);
    return bfs(n, graph);
}
public void buildGraph(int n, int[][] edges, HashMap<Integer, ArrayList<Integer>> graph) {
    for(int i = 0; i < n; i++) {
        graph.put(i, new ArrayList<Integer>());
    }
    for(int i = 0; i < edges.length; i++) {
        graph.get(edges[i][0]).add(edges[i][1]);
        graph.get(edges[i][1]).add(edges[i][0]);
    }
}
public boolean bfs(int n, HashMap<Integer, ArrayList<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<Integer>();
    HashSet<Integer> visited = new HashSet<Integer>();
    queue.offer(0);
    while(!queue.isEmpty()) {
        int tmp = queue.poll();
        if(visited.contains(tmp)) {
            return false;
        }
        visited.add(tmp);
        for(Integer i : graph.get(tmp)) {
            if(!visited.contains(i)) {
                queue.offer(i);
            }
        }
    }
    if(visited.size() != n) {
        return false;
    }
    return true;
}

Solution 3: Union Find.

class UnionFind {
    int[] arr;
    public UnionFind(int n) {
        arr = new int[n + 1];
        for(int i = 1; i <= n; i++) {
            arr[i] = i;
        }
    }
    public void union(int n1, int n2) {
        int p1 = find(n1);
        int p2 = find(n2);
        if(p1 != p2) {
            arr[p1] = arr[p2];
        }
    }
    public int find(int n) {
        if(n != arr[n]) {
            int father = find(arr[n]);
            return father;
        }
        return n;
    }
}
public boolean validTree(int n, int[][] edges) {
    if(edges.length != n - 1) {
        return false;
    }
    UnionFind uf = new UnionFind(n);
    for(int i = 0; i < edges.length; i++) {
        if(uf.find(edges[i][0]) == uf.find(edges[i][1])) {
            return false;
        }
        uf.union(edges[i][0], edges[i][1]);
    }
    return true;
}