[LintCode] 432 Find the Weak Connected Component in the Directed Graph 解题报告

Description
Find the number Weak Connected Component in the directed graph. Each node in the graph contains a label and a list of its neighbors. (a connected set of a directed graph is a subgraph in which any two vertices are connected by direct edge path.)

Notice
Sort the element in the set in increasing order


Example
Given graph:

A----->B  C
  \          |   |
    \        |   |
      \      |   |
        \   v  v
       ->D  E <- F
Return {A,B,D}, {C,E,F}. Since there are two connected component which are {A,B,D} and {C,E,F}


思路
这题和Connected Component in Undirected Graph其实是一模一样的。
唯一的区别是这题是有向图。所以不能用BFS做。用union-find来做就和上面这题一样了。
这题的UF由于上来不知道点的值的大小，所以不能开一个数组，只能用HashMap来实现。
把所有的点和对应的root存进HashMap。
最后需要输出结果的时候，把相同root的点放进同一个list。最后把每个list排个序。


Code

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    /**
     * @param nodes a array of Directed graph node
     * @return a connected set of a directed graph
     */
     
    public class UF {
        public HashMap<Integer, Integer> root;
        
        public UF(HashSet<Integer> hash) {
            root = new HashMap<>();
            for (Integer nodeLabel : hash) {
                root.put(nodeLabel, nodeLabel);
            }
        }
        
        public int find(int nodeLabel) {
            while (nodeLabel != root.get(nodeLabel)) {
                root.put(root.get(nodeLabel), root.get(root.get(nodeLabel)));
                nodeLabel = root.get(nodeLabel);
            }
            return nodeLabel;
        }
        
        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            if (i != j) {
                root.put(root.get(i), j);
            }
        }
    }
    
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        // Write your code here
        
        HashSet<Integer> hash = new HashSet<>();
        for (DirectedGraphNode node : nodes) {
            hash.add(node.label);
        }
        
        UF uf = new UF(hash);
        
        for (DirectedGraphNode node : nodes) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                uf.union(node.label, neighbor.label);
            }
        }
        
        return print(uf, hash);
    }
    
    public List<List<Integer>> print(UF uf, HashSet<Integer> hash) {
        
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        
        for (Integer nodeLabel : hash) {
            int root = uf.find(nodeLabel);
            if (!map.containsKey(root)) {
                List<Integer> list = new ArrayList<>();
                list.add(nodeLabel);
                map.put(root, list);
            }
            else {
                map.get(root).add(nodeLabel);
            }
        }
        
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> list : map.values()) {
            Collections.sort(list);
            res.add(list);
        }
        
        return res;
    }
}