LintCode 432 - Find the Weak Connected Component in the Directed Graph


Related: Lintcode 431 - Find the Connected Component in the Undirected Graph
https://xuezhashuati.blogspot.com/2017/03/lintcode-432-find-weak-connected_24.html
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}

* Definition for Directed graph.
* class DirectedGraphNode {
*     int label;
*     ArrayList<DirectedGraphNode> neighbors;
*     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
* };
这题和Connected Component in Undirected Graph其实是一模一样的。
唯一的区别是这题是有向图。所以不能用BFS做。用union-find来做就和上面这题一样了。
这题的UF由于上来不知道点的值的大小,所以不能开一个数组,只能用HashMap来实现。
把所有的点和对应的root存进HashMap。
最后需要输出结果的时候,把相同root的点放进同一个list。最后把每个list排个序。

    public class UF {
        public HashMap<Integer, Integer> root;
        
        public UF(HashSet<Integer> hash) {
            root = new HashMap<>();
            for (Integer nodeLabel : hash) {
                root.put(nodeLabel, nodeLabel);
            }
        }
        
        public int find(int nodeLabel) {
            while (nodeLabel != root.get(nodeLabel)) {
                root.put(root.get(nodeLabel), root.get(root.get(nodeLabel)));
                nodeLabel = root.get(nodeLabel);
            }
            return nodeLabel;
        }
        
        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            if (i != j) {
                root.put(root.get(i), j);
            }
        }
    }
    
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        // Write your code here
        
        HashSet<Integer> hash = new HashSet<>();
        for (DirectedGraphNode node : nodes) {
            hash.add(node.label);
        }
        
        UF uf = new UF(hash);
        
        for (DirectedGraphNode node : nodes) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                uf.union(node.label, neighbor.label);
            }
        }
        
        return print(uf, hash);
    }
    
    public List<List<Integer>> print(UF uf, HashSet<Integer> hash) {
        
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        
        for (Integer nodeLabel : hash) {
            int root = uf.find(nodeLabel);
            if (!map.containsKey(root)) {
                List<Integer> list = new ArrayList<>();
                list.add(nodeLabel);
                map.put(root, list);
            }
            else {
                map.get(root).add(nodeLabel);
            }
        }
        
        List<List<Integer>> res = new ArrayList<>();
        for (List<Integer> list : map.values()) {
            Collections.sort(list);
            res.add(list);
        }
        
        return res;
    }

http://www.cnblogs.com/Dylan-Java-NYC/p/6364620.html
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).
 3  * class DirectedGraphNode {
 4  *     int label;
 5  *     ArrayList<DirectedGraphNode> neighbors;
 6  *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 7  * };
10     public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
11 
12         List<List<Integer>> res = new ArrayList<List<Integer>>();
13         if(nodes == null || nodes.size() == 0){
14             return res;
15         }
16         
17         HashSet<Integer> hs = new HashSet<Integer>();
18         for(DirectedGraphNode node : nodes){
19             hs.add(node.label);
20             for(DirectedGraphNode neigh : node.neighbors){
21                 hs.add(neigh.label);
22             }
23         }
24         
25         UnionFind forest = new UnionFind(hs);
26         for(DirectedGraphNode node : nodes){
27             for(DirectedGraphNode neigh : node.neighbors){
28                 forest.union(node.label, neigh.label);
29             }
30         }
31         
32         HashMap<Integer, List<Integer>> resHashMap = new HashMap<Integer, List<Integer>>();
33         for(int i : hs){
34             //找到root
35             int rootParent = forest.root(i);
36             if(!resHashMap.containsKey(rootParent)){
37                 resHashMap.put(rootParent, new ArrayList<Integer>());
38             }
39             //每个root下面的值都放在一个list里,包括root本身
40             resHashMap.get(rootParent).add(i);
41         }
42         
43         for(List<Integer> item : resHashMap.values()){
44             Collections.sort(item);
45             res.add(item);
46         }
47         return res;
48     }
49 }
50 
51 class UnionFind{
52     
53     //HashMap maintaining key - > value (child -> parent) relationship
54     HashMap<Integer, Integer> parent;
55     public UnionFind(HashSet<Integer> hs){
56         parent = new HashMap<Integer, Integer>();
57         for(int i : hs){
58             parent.put(i, i);
59         }
60     }
61     
62     public int root(int i){
63         while(i != parent.get(i)){
64             parent.put(i, parent.get(parent.get(i)));
65             i = parent.get(i);
66         }
67         return i;
68     }
69     
70     public void union(int i, int j){
71         int p = root(i);
72         int q = root(j);
73         if(p != q){
74             parent.put(p, q);
75         }
76     }
https://wxx5433.gitbooks.io/interview-preparation/content/part_ii_leetcode_lintcode/union_find/find_the_weak_connected_component_in_the_directed_graph.html
Time: O(NlgN)
Space: O(N)
  Map<Integer, Integer> rootMap = new HashMap<>();
  public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
    List<List<Integer>> result = new ArrayList<>();
    // initialize the node to different component.
    for (DirectedGraphNode node : nodes) {
      rootMap.put(node.label, node.label);
    }
    // union
    for (DirectedGraphNode node : nodes) {
      for (DirectedGraphNode neighbor : node.neighbors) {
        union(node.label, neighbor.label);
      }
    }
    // put nodes in the same component together.
    Map<Integer, List<Integer>> components = new HashMap<>();
    for (DirectedGraphNode node : nodes) {
      List<Integer> nodesList;
      int root = find(node.label);
      if (components.containsKey(root)) {
        nodesList = components.get(root);
      } else {
        nodesList = new ArrayList<>();
      }
      nodesList.add(node.label);
      components.put(root, nodesList);
    }
    // generate result
    for (List<Integer> nodesList : components.values()) {
      result.add(nodesList);
    }
    return result;
  }

  // Union-find methods
  private int find(int label) {
    while (label != rootMap.get(label)) {
      rootMap.put(label, rootMap.get(label));  // path compression
      label = rootMap.get(label);
    }
    return label;
  }

  private void union(int label1, int label2) {
    int root1 = find(label1);
    int root2 = find(label2);
    rootMap.put(root1, root2);
  }
Still union-find, just not use it explicitly
http://cherylintcode.blogspot.com/2015/07/find-weak-connected-component-in.html
    public List<List<Integer>> connectedSet2(ArrayList<DirectedGraphNode> nodes) {
        // Write your code here
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(DirectedGraphNode node : nodes){
            for(DirectedGraphNode n : node.neighbors){
                int fa = find(map, node.label);
                int ch = find(map, n.label);
                map.put(fa, ch);
            }
        }
        HashMap<Integer, ArrayList<Integer>> record = new HashMap<Integer, ArrayList<Integer>>();
       
        for(DirectedGraphNode node : nodes){
            int val = find(map, node.label);
            if(!record.containsKey(val)){
                record.put(val, new ArrayList<Integer>());
            }
            record.get(val).add(node.label);
        }
       
        for(int key : record.keySet()){
            ArrayList<Integer> sub = new ArrayList<Integer>();
            sub.addAll(record.get(key));
            res.add(sub);
        }
        return res;
       
    }
   
    private int find(HashMap<Integer, Integer> map, int v){
        if(!map.containsKey(v)){
            map.put(v, v);
            return v;
        }
        while(map.get(v) != v) v = map.get(v);
        return v;
    }

https://github.com/shawnfan/LintCode/blob/master/Java/Find%20the%20Weak%20Connected%20Component%20in%20the%20Directed%20Graph.java
看到了weak component的形式: 一个点指向所有,那么所有的点都有一个公共的parent,然后就是要找出这些点。 

为何不能从一个点出发,比如A,直接print它所有的neighbors呢?   
不行,如果轮到了B点,那因为是directed,它也不知道A的情况,也不知道改如何继续加,或者下手。 

所以,要把所有跟A有关系的点,或者接下去和A的neighbor有关系的点,都放进union-find里面,让这些点有Common parents.   

最后output的想法: 
做一个 map <parent ID, list>。 
之前我们不是给每个num都存好了parent了嘛。 
每个num都有个parent, 然后不同的parent就创造一个不同的list。 
最后,把Map里面所有的list拿出来就好了。 

当然这种题目DFS和BFS也都可以做
https://www.jiuzhang.com/qa/3098/
I recently had an interview and the interviewer asked me not to use Union-Find.
http://cherylintcode.blogspot.com/2015/07/find-weak-connected-component-in.html

X. DFS
https://www.jiuzhang.com/qa/2357/
可以用DFS,但是你先得把有向图处理成无向图。
比如C--->E,显然E无法找到C,但是他们是一个连通块的。如果你DFS的时候先遇到了E,那么C可能就无法包含到当前这个连通块中,所以需要把有向的边处理成无向的,这样就可以使用DFS去处理了。复杂度也是O(n + m) 
n, m 分别代表点数和边数
https://github.com/gky2009514/lintcode/blob/master/C%2B%2B/432_Find%20the%20Weak%20Connected%20Component%20in%20the%20Directed%20Graph.cpp
Convert Directed Graph to (kind of ) undirected Graph
vector<vector<int>> connectedSet2(vector<DirectedGraphNode*>& nodes) {
    if (nodes.size() == 0)
        return vector<vector<int> >();
    for (int i = 0; i < nodes.size(); i++) {
        for (int j = 0; j < nodes[i]->neighbors.size(); j++) {
            if (nodes[i]->neighbors[j] == nodes[i])
                continue;
            nodes[i]->neighbors[j]->neighbors.push_back(nodes[i]);
        }
    }
    mp.clear();
    res.clear();
    vector<int> nset;
    for (int i = 0; i < nodes.size(); i++) {
        if (mp.find(nodes[i]) == mp.end()) {
            nset.clear();
            dfs(&nodes[i], nset);
            res.push_back(nset);
        }
    }
    for (int i = 0; i < res.size(); i++)
        sort(res[i].begin(), res[i].end());
    return res;
}

private:
map<DirectedGraphNode*, bool> mp;
vector<vector<int> > res;

void dfs(DirectedGraphNode** node, vector<int> &nset) {
    nset.push_back((*node)->label);
    mp[*node] = true;
    for (int i = 0; i < (*node)->neighbors.size(); i++) {
        if (mp.find((*node)->neighbors[i]) == mp.end())
            dfs(&((*node)->neighbors[i]), nset);
    }
}


有向图强联通,是需要tarjan算法来做的 (0)

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts