算法小结 -- Union Find的套路

Union Find
Good for graph problem, like finding cycles in edge, largest components, etc

O(M) for union find, M operations

M quick union + path compression on N objects should be N + MlgN

-make set
-union
-find set
思路：-- for n nodes from 0 to n-1, create roots[n] to track each root's parents. 
         -- initialize parent with -1(point to null), roots = [-1,-1,-1,...-1],
 eg: n nodes from 0 to n-1, edges[0,1] [0,2] [2,3] will be [1,2,3,-1...]
         -- recursively find root1 and root2 (edge[root1,root2])check if they are in the same set
 if found in two sets, then union: roots[root1] = root2;
         -- middle roots can be dirty, keep updating&maintain top parents or boundaries.
         -- use path compression(point child root directly to top parent) to save time 
               
应用: Undirected Graph 

EX: 
» 323. Number of Connected Components in an Undirected Graph(Union Find) G家Twitter
http://rainykat.blogspot.com/2017/01/leetcodegtwitter-323-number-of.html
» 261. Graph Valid Tree(Union Find)G家F家
http://rainykat.blogspot.com/2017/01/leetcodegf-261-graph-valid-treeunion.html
» 128. Longest Consecutive Sequence G家F家 
http://rainykat.blogspot.com/2017/01/leetcodefg-128-longest-consecutive.html