Graph Valid Tree

2/16/2018 update

Loop through edges, connect nodes parents with union find. If their parents are equal, so there is a loop. Remember to check edges.length == n - 1, Union find can not check number of edges iterated.

Solution:
Still need to do path compression. It's faster.

class Solution {
    public boolean validTree(int n, int[][] edges) {
        int[] roots = new int[n];
        for (int  i = 0; i < n; i++) {
            roots[i] = i;
        }
        for (int[] edge: edges) {
            int x = find(roots, edge[0]);
            int y = find(roots, edge[1]);
            if (x == y)
                return false;
            roots[x] = y;
        }
        return edges.length == n -1;
    }

    private int find(int[] roots, int n) {
            if (roots[n] != n) roots[n] = find(roots, roots[n]);
            return roots[n];
    }
}

----------------------------------------------------------------------------------------------------------------
2/15/2018 update
直接判断edge.length和n的方法其实是作弊。如果有环在bfs就会重复访问。


------------------------------------------------------------------------------------------------------------------------
1/31/2018
The edges.length != n - 1 rules out the case that all nodes are connected but has cycle. But there are nodes that not been connected. So we use BFS to traverse the graph to check whether we can get n nodes.
Solution:
Below is the level order traversal, can be used to get distance.

class Solution {
    public boolean validTree(int n, int[][] edges) {
        if (edges == null || edges.length != n - 1)
            return false;
        
        Map<Integer, List<Integer>> graph = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());    
        } 
        
        for (int i = 0; i < edges.length; i++) {
            int x = edges[i][0];
            int y = edges[i][1];
            
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        
         Queue<Integer> queue = new LinkedList<>();  
         Set<Integer> res = new HashSet<>();  
         queue.offer(0);  
       
        
        while (!queue.isEmpty()) {  
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                if (!res.contains(cur)) {
                    res.add(cur);
                    for (int j: graph.get(cur)) {
                        queue.offer(j);
                    }
                }
                
            } 
        }  
        
        return res.size() == n;      

    }
}

A more concise way:

        queue.add(0);
        nodes.add(0);
        while(!queue.isEmpty())
        {
            int node = queue.remove();
            Set<Integer> neighbours = graph.get(node);
            for(int neib: neighbours)
            {
                if(nodes.contains(neib))
                    continue;
                nodes.add(neib);
                queue.add(neib);
            }
        }

思路：
首先要搞清楚树的定义，要满足2个条件 1: 边的数量是 n-1. 2. 必须是联通的，也就是说用BFS遍历可以获取所有的node。 可以用一个hashset来保存遍历过的node，每一次加新的node检查是否加过。

还需要把没一个节点的邻居都找出来存在hashset里面。代码如下

  private Map<Integer, Set<Integer>> initializeGraph(int[][] edges, int n)  
   {  
     Map<Integer, Set<Integer>> graph = new HashMap<>();  
     for(int i=0; i<n; i++)  
     {  
       graph.put(i, new HashSet<Integer>());  
     }  
     for(int i=0; i<edges.length; i++)  
     {  
       int x = edges[i][0];  
       int y = edges[i][1];  
       graph.get(x).add(y);  
       graph.get(y).add(x);  
     }  
     return graph;  
   }  

实现：
 注意queu和结果hashset要同时更新。在初始化hashmap的时候，这样就行了Map> graph = new HashMap<>();不需要把HashMap里面的类型都定义出来，不然会报错。