261. Graph Valid Tree

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree.

For example:

Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

Note: you can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

This is an undirected map, so in-degree methods is not very suitable. Using bfs, since in a valid tree traversal, each not should be only visited once, if there is a loop, you end up visit an already visited node, this is not a valid tree. using a queue, every time, if node is not visited, mark it as visited, then traverse its neighbors, if is not visited, enque it, if there is any cycle in the graph, your queue ends up containing multiple instance of certain numbers.

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        List<List<Integer>> list = new ArrayList<>();
        for(int i=0; i<n; i++){
            list.add(new ArrayList<>());
        }
        for(int[] edge : edges){
            list.get(edge[0]).add(edge[1]);
            list.get(edge[1]).add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while(!queue.isEmpty()){
            int id = queue.poll();
            if(visited[id]){
                return false;
            }
            visited[id] = true;
            for(int neighbor : list.get(id)){
                if(!visited[neighbor]){
                    queue.offer(neighbor);
                }
            }
        }

        for(boolean b : visited){
            if(!b) return false;
        }
        return true;
    }
}

This question can be viewed in different perspective, building a set, initially each node has its own set, with more edges coming, merge two related sets, until the set remain equals to 1. this union-find algorithm.

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

        for(int[] e : edges){
            int u = e[0];
            int v = e[1];
            if(id[u] == id[v]) return false;
            merge(id, u, v);
        }
        for(int i=1; i<n; i++){
            if(id[i-1] != id[i]) return false;
        }

        return true;
    }

    void merge(int[] id, int u, int v){
        int t = id[u];
        for(int i=0; i< id.length; i++){
            if(id[i] == t) id[i] = id[v]; // if id[i] == id[u] MAY NOT WORK, cause the id[u] val may changed.
        }
    }
}