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

Have you met this question in a real interview?

Yes

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}

1, 可用BFS或DFS. 用union find （需要用Hashmap实现，因为可能有负值

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */

class UnionFind {
    private HashMap<Integer, Integer> father = null;
    public UnionFind(HashSet<Integer> set) {
        father = new HashMap<Integer, Integer>();
        for (Integer item : set) {
            father.put(item, item);
        }
    }

    public int find(int a) {
        int parent = father.get(a);

        while (parent != father.get(parent)) {
            parent = father.get(parent);
        }

        int temp = -1;
        int fa = father.get(a);
        while (fa != parent) {
            temp = father.get(fa);
            father.put(fa, parent);
            fa = temp;
        }

        return parent;
    }

    public void connect(int a, int b) {
        int root_a = find(a);
        int root_b = find(b);
        if (root_a != root_b) {
            father.put(root_a, root_b);
        }
    }
}


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>> ans = new ArrayList<>();
        HashSet<Integer> set = new HashSet<Integer>();
        for (DirectedGraphNode node : nodes) {
            set.add(node.label);
            for (DirectedGraphNode neighbor : node.neighbors) {
                set.add(neighbor.label);
            }
        }

        UnionFind uf = new UnionFind(set);

        for (DirectedGraphNode node : nodes) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                uf.connect(node.label, neighbor.label);
            }
        }

        HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        for (Integer cur : set) {
            if (uf.find(cur) == cur) {
                map.put(cur, new HashSet<Integer>());
            }
        }

        for (Integer cur : set) {
            map.get(uf.find(cur)).add(cur);
        }

        for (HashSet<Integer> values : map.values()) {
            List<Integer> current = new ArrayList<>();
            for (Integer cur : values) {
                current.add(cur);
            }
            Collections.sort(current);
            ans.add(current);
        }
        return ans;
    }
}