Lintcode 432. 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 weak connected component of a directed graph is a maximum subgraph in which any two vertices are connected by direct edge path.)

Example

Example 1:

Input: {1,2,4#2,4#3,5#4#5#6,5}
Output: [[1,2,4],[3,5,6]]
Explanation:
  1----->2    3-->5
   \     |        ^
    \    |        |
     \   |        6
      \  v
       ->4

Example 2:

Input: {1,2#2,3#3,1}
Output: [[1,2,3]]

Notice

Sort the elements of a component in ascending order.

Code (Java):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109

/**  * 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) {         List<List<Integer>> ans = new ArrayList<>();         if (nodes == null || nodes.size() == 0) {             return ans;         }                   // note: the label is not from 1 to n         //         Set<Integer> set = new HashSet<>();                   for (DirectedGraphNode node : nodes) {             set.add(node.label);             for (DirectedGraphNode neighbor : node.neighbors) {                 set.add(neighbor.label);             }         }                   UF uf = new UF(set);           // union find         //         for (DirectedGraphNode node : nodes) {             int labelA = node.label;             for (DirectedGraphNode neighbor : node.neighbors) {                 int labelB = neighbor.label;                                   int rootA = uf.find(labelA);                 int rootB = uf.find(labelB);                                   if (rootA != rootB) {                     uf.union(rootA, rootB);                 }             }         }                   return uf.getCC();     }       }   class UF {     Map<Integer, Integer> parents;     Set<Integer> set;           public UF(Set<Integer> set) {         this.parents = new HashMap<>();         this.set = set;                   for (int num : set) {             parents.put(num, num);         }     }           public int find(int a) {         int root = a;                   while (root != parents.get(root)) {             root = parents.get(root);         }                   while (root != a) {             int temp = parents.get(a);             parents.put(a, root);             a = temp;         }                   return root;     }           public void union(int a, int b) {         parents.put(b, a);     }           public List<List<Integer>> getCC() {         List<List<Integer>> ans = new ArrayList<>();         Map<Integer, List<Integer>> map = new HashMap<>();                     for (int i : set) {             int root = find(i);             List<Integer> list = map.getOrDefault(root, new ArrayList<>());             list.add(i);             map.put(root, list);         }                   for (int key : map.keySet()) {             List<Integer> list = map.get(key);             Collections.sort(list);             ans.add(list);         }                   return ans;     } }

Analysis:
Note that we should build the result of CC at last. That's because the root of a node might change along with connecting the nodes. 

Why note DFS for this problem? That's because it's a directed graph. We need to change to undirected graph first in order to use DFS.