求教Airbnb的graph traversal问题

scarlettzzhang 发表于 2018-2-19 16:51
这题写个Union Find应该也可以吧？return number of connected component

我也觉得union find可解，不知道有没有更高效的方法 因为普通写法的find复杂度也比较高？

leetcode上是不是还没有这道题？

这个题 目前可行的应该只有强连通分量缩环的方法（个人觉得也只有这个方法能到O(n))
楼上其他方法的都不大可行。多想想复杂的例子 肯定过不了的。

这不是 minimized spanning tree就是shortest path, 路径的value是0？

先去环 之后topological sort找入度为0的点应该可解 union find应该不行因为每个路径的点集不是单纯的disjoint set 一个点可以有多个入度为0的parent

对于这个给定的有向图，答案是什么？1 或 2？

1. private void DFS(Set<Integer> visited, int index, List<Integer> ret, Map<Integer, Set<Integer>> hash) {
   
2.         visited.add(index);
   
3.         for(int val: hash.getOrDefault(index, new HashSet<>())) {
   
4.             if(ret.contains(val)) ret.remove(val);
   
5.             if(!visited.contains(val)) {
   
6.                 DFS(visited, val, ret, hash);
   
7.             }
   
8.         }
   
9.     }
   
10. 
    
11.     public List<Integer> findMin(int[][] edges, int n) {
    
12.         Map<Integer, Set<Integer>> hash = new HashMap<>();
    
13.         for(int[] edge: edges) {
    
14.             if(edge[0] == edge[1]) continue;
    
15.             hash.computeIfAbsent(edge[0], k -> new HashSet<>()).add(edge[1]);
    
16.         }
    
17.         Set<Integer> visited = new HashSet<>();
    
18.         List<Integer> ret = new ArrayList<>();
    
19.         for(int i = 0; i <= n; i++) {
    
20.             if(visited.contains(i)) continue;
    
21.             ret.add(i);
    
22.             DFS(visited, i, ret, hash);
    
23.         }
    
24.         return ret;
    
25.     }
    

复制代码

mren 发表于 2019-3-18 15:26
[mw_shl_code=java,true]private void DFS(Set visited, int index, List ret, Map hash) {
        visit ...

if(ret.contains(val)) ret.remove(val);

补充内容 (2019-3-19 06:13):
这行好棒，这样就不用合并 SCC了。。

补充内容 (2019-3-19 06:22):
如果 图里面有个 环呢 ？  比如：0-> 1,  and 0 -> 1 .  你的答案是0.

seaskymonster 发表于 2019-3-19 06:13
if(ret.contains(val)) ret.remove(val);

补充内容 (2019-3-19 06:13):

0 -> 1
1 -> 0
的话是一个环，首先访问0，然后DFS的时候会访问到1，然后当继续DFS的时候访问0，但是0被标记了，这样就结束了，结果就是0