lintcode 432. 找出有向图中的弱联通分量

中等题，lintcode
利用并查集来把每个集合的node 给确定起来， 首先建立并查集结构，然后利用connect方法把所有的点都归在各自的大集合下。

最后遍历一遍点，根据集合将统一联通块内的点加入到一个list，这样就可以得到结果
代码如下

/**
 * 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 List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        // write your code here
        List<List<Integer>> res = new ArrayList<>();
        if(nodes == null || nodes.size() == 0){
            return res;
        }
        List<Integer> list = new ArrayList<>();
        for(DirectedGraphNode node:nodes){
            list.add(node.label);
        }
        UnionFind uf = new UnionFind(list);
        
        //对所有的点进行归类处理
        for(DirectedGraphNode node: nodes){
            for(DirectedGraphNode nei: node.neighbors){
                uf.connect(nei.label, node.label);
            }
        }
        // set里面存放集合编号
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i <nodes.size(); i++){
            System.out.println(uf.find(nodes.get(i).label));
            if(!set.contains(uf.find(nodes.get(i).label))){
                set.add(uf.find(nodes.get(i).label));
                int label = uf.find(nodes.get(i).label);
                List<Integer> ls = new ArrayList<>();
                for(int j = 0; j <nodes.size(); j++ ){
                    if(uf.find(nodes.get(j).label) == label){
                        ls.add(nodes.get(j).label);
                    }
                }
                res.add(ls);
            }
        }
        return res;
    }
}
class UnionFind{
    Map<Integer, Integer> map = new HashMap<>();
 
    public UnionFind(List<Integer> ls){
        for(int a: ls){
            map.put(a, a);
        }
    }
    
    int find(int x){
        if(map.get(x) == x){
            return x;
        }
        int f = find(map.get(x));
        map.put(x, f);
        return map.get(x);
    }
    
    void connect(int a, int b){
        int f_a = find(a);
        int f_b = find(b);
        
        if(f_a != f_b){
            map.put(f_a, f_b);
        }
    }
}