Leetcode/G家F家 -- 261. Graph Valid Tree(Union Find)

261. Graph Valid Tree(Union Find)

• Difficulty: Medium

https://leetcode.com/problems/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.

 Google Facebook Zenefits

Tree: Any connected graph w/o cycle
思路： 1. Union find: for each interval, start's set and end's set should be in different set.
               If in same set, there is cycle. Start and end find its set recursively tot the top parents where nums[i] is -1. Once in 2 sets(top parent not equal), union 2 set by setting start's top parent be end.
(nums[start's top parent] = end's top parent)
               Exit loop with no loop, judge if (nodes number -1 = edge number) to ensure connected graph

 Complexity: say the graph has V vertices and E edges, the find( ) function takes O(V) time because in the worst case it has to go through all the vertices, and from outside we loop through all the edges, so the time complexity should be O(V*E).

public class Solution {
    public boolean validTree(int n, int[][] edges) {
        // initialize n isolated islands
        int[] roots = new int[n];
        Arrays.fill(roots, -1);
        
        // perform union find,if start & end in same set, means cycle
        for (int i = 0; i < edges.length; i++) {
            int root1 = findSet(roots,edges[i][0]);//when union, always update the top parent(recur)
            int root2 = findSet(roots,edges[i][1]);
            if(root1 == root2)//in same set=find cycle
                return false;
            roots[root1] = root2;//union, must be root1, don't forget mid nodes traveled when find top parents
        }
        
        return edges.length == n - 1;//no cycle but still need check if # of nodes equals # of edges
    }
    public int findSet(int[] roots,int i){
        if(roots[i]==-1)return i;//is top parent
        return findSet(roots,roots[i]);
    }
}