Leetcode/G家twitter -- 323. Number of Connected Components in an Undirected Graph (Union Find)

323. Number of Connected Components in an Undirected Graph(Union Find)

• Difficulty: Medium

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/

iven 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 find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

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

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

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

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.

参考：https://discuss.leetcode.com/topic/32752/easiest-2ms-java-solution

This is 1D version of Number of Islands II. For more explanations, check out this 2D Solution.

1. n points = n islands = n trees = n roots.
2. With each edge added, check which island is e[0] or e[1] belonging to.
3. If e[0] and e[1] are in same islands, do nothing.
4. Otherwise, union two islands, and reduce islands count by 1.
5. Bonus: path compression can reduce time by 50%.

Hope it helps!

Complexity: The complexity for M quick union + path compression on N objects should be N + MlgN, I think in this problem, M = 2E, N = V, so O(V + 2ElgV)

public class Solution {
    public int countComponents(int n, int[][] edges) {
         // initialize n isolated islands
        int[] roots = new int[n];
        for(int i = 0; i < n; i++) roots[i] = i; 
        int count =n;
        // perform union find
        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 in one set means already reduce count by adding edge before, new edge not impact
            if(root1!=root2){
                roots[root1] = root2;//in 2 sets,union(add a edge)
                count--;
            }
        }
        return count;
    }
    public int findSet(int[] roots,int i){
        if(roots[i]==i)return i;//is top parent
        roots[i] = findSet(roots,roots[i]);//path compression(optional)
        return roots[i];
    }
}

Optional path compression: (Iteration has little difference from recursion)

public int findSet(int[] roots,int i){
        while(roots[i] != i) {
            roots[i] = roots[roots[i]];  // optional: path compression
            i = roots[i];
        }
        return i;
    }

算法小结 -- 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

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]);
    }
}

       

Leetcode/F家，G家 -- 128. Longest Consecutive Sequence(HashMap+UnionFind)

128. Longest Consecutive Sequence

• Difficulty: Hard

https://leetcode.com/problems/longest-consecutive-sequence/

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity

参考： https://discuss.leetcode.com/topic/6148/my-really-simple-java-o-n-solution-accepted/34

思路： Use HashMap to store val and its current length of consecutive elements(not necessarily final),

only updating and maintain max length on boundary points(n-left & n+right). 

Complexity: O(N)

public class Solution {
    public int longestConsecutive(int[] num) {
        int len = 0;
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();//<val,len>
        for(int n:num){
            if(!map.containsKey(n)){
                //1.check if n has conseq and update len
                int left = (map.containsKey(n-1))?map.get(n-1):0;
                int right = (map.containsKey(n+1))?map.get(n+1):0;
                int sum = left + right +1;
                map.put(n,sum);
                len = Math.max(sum,len);
                // 2.Union by only updating boundary(maintaining total len)
                // Leave middle k-v dirty to avoid cascading update
                map.put(n-left,sum);
                map.put(n+right,sum);
            }else{
                //duplicates
                continue;
            }
        }
        return len;
    }
}