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):

/**
 * 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.