Massive Algorithms: LintCode 432 - Find the Weak Connected Component in the Directed Graph

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)

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

Labels

Popular Posts