LintCode Find the Weak Connected Component in the Directed Graph

?原題鏈接在這里：http://www.lintcode.com/en/problem/find-the-weak-connected-component-in-the-directed-graph/

題目：

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}

題解：

是Union Find類題目. 用HashMap 的key -> value對應關系來維護child -> parent關系.

對于每一組node -> neighbor都當成 child -> parent的關系利用forest union起來.

再用resHashMap 來記錄每一個root 和 這個root對應的所有children, 包括root本身, 對應關系.

最后把resHashMap.values() 挨個排序后加到res中.

Time Complexity: O(nlogn). n=hs.size(). 就是所有點的個數.

得到hs用了O(n). forest union用了 O(nlogn). 得到resHashMap用了O(nlogn). 得到res用了O(nlogn).

Space: O(n).

AC Java:

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
public class Solution {
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {

        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(nodes == null || nodes.size() == 0){
            return res;
        }
        
        HashSet<Integer> hs = new HashSet<Integer>();
        for(DirectedGraphNode node : nodes){
            hs.add(node.label);
            for(DirectedGraphNode neigh : node.neighbors){
                hs.add(neigh.label);
            }
        }
        
        UnionFind forest = new UnionFind(hs);
        for(DirectedGraphNode node : nodes){
            for(DirectedGraphNode neigh : node.neighbors){
                forest.union(node.label, neigh.label);
            }
        }
        
        HashMap<Integer, List<Integer>> resHashMap = new HashMap<Integer, List<Integer>>();
        for(int i : hs){
            //找到root
            int rootParent = forest.root(i);
            if(!resHashMap.containsKey(rootParent)){
                resHashMap.put(rootParent, new ArrayList<Integer>());
            }
            //每個root下面的值都放在一個list里，包括root本身
            resHashMap.get(rootParent).add(i);
        }
        
        for(List<Integer> item : resHashMap.values()){
            Collections.sort(item);
            res.add(item);
        }
        return res;
    }
}

class UnionFind{
    
    //HashMap maintaining key - > value (child -> parent) relationship
    HashMap<Integer, Integer> parent;
    public UnionFind(HashSet<Integer> hs){
        parent = new HashMap<Integer, Integer>();
        for(int i : hs){
            parent.put(i, i);
        }
    }
    
    public int root(int i){
        while(i != parent.get(i)){
            parent.put(i, parent.get(parent.get(i)));
            i = parent.get(i);
        }
        return i;
    }
    
    public void union(int i, int j){
        int p = root(i);
        int q = root(j);
        if(p != q){
            parent.put(p, q);
        }
    }
}

類似Number of Connected Components in an Undirected Graph.