求教Airbnb的graph traversal问题

mren 发表于 2019-3-19 11:37
0 -> 1
1 -> 0
的话是一个环，首先访问0，然后DFS的时候会访问到1，然后当继续DFS的时候访问0，但是0被 ...

我觉得这里有两个问题（我理解的ret是存start node in a SCC）
1：在line 21你先把i加到了ret 里面，在你描述的从1访问0的情况下，在line 4这个在ret 里面的0，会先被删掉，然后才检查是不是要继续dfs。这个就是seaskymonster 说的结果是0的情况

2. 假设我们 先dfs 再 把这个start node （0） 加入到ret里面。那么比如这个例子，0 <-> 1 <- 2
如果从0开始，那么就是 0 -> 1， 然后 1->0发现 0 已经visited ，所以退出，那么visited = (0, 1) ret = (0)
但是当从2开始时，因为1已经在visited里面了所以不会走到0，也就不会去删除在ret里面的0，所以结果为2，也是不对



根据这个思路，需要解决以上两个问题 1. 不能把current start node自己删了，2. 能够可以访问到以前的start_node然后可以删除掉
解决1其实就是先看以当前v为start，能dfs到哪些点，包括start自己，然后删掉出现在ret里面的，也就是以前的start node（已经被最新的覆盖）最后删除完了，再把自己加上
解决2需要保证以当前v为start的时候，即使碰到了之前visit 过的scc，我们也要进去走一圈，看看哪个是以前的start

这个解法我试了试几个test case结果都是对的，大家给分析一下？
我用python写的代码贴在下面

您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 110 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Popular Interview Questions from Top Companies

ericliu03 发表于 2019-3-21 07:14
我觉得这里有两个问题（我理解的ret是存start node in a SCC）
1：在line 21你先把i加到了ret 里面，在 ...

赞认真！请考虑楼上magicsets和其它几楼。

ericliu03 发表于 2019-3-21 07:14
我觉得这里有两个问题（我理解的ret是存start node in a SCC）
1：在line 21你先把i加到了ret 里面，在 ...

感觉你的解法是O(n)的，带剪枝并不是爆搜:)
对于这道题看到很多人推崇scc Kosaraju 看的也是挺懵逼的，难道这道题直接类似LC200中DFS的解法有什么问题吗？贴上了层主的解法加上楼主test case的一些变化，欢迎大家猛喷提出其他的test case：）

1. from collections import defaultdict
   
2. 
   
3. def dag_traverse(edges):
   
4.     graph = defaultdict(list)
   
5.     vertex = set()
   
6.     for start, end in edges:
   
7.         graph[start].append(end)
   
8.         vertex.add(start)
   
9.         vertex.add(end)
   
10. 
    
11.     visited = set()
    
12.     res = 0
    
13.     for each in vertex:
    
14.         if each not in visited:
    
15.             visited.add(each)
    
16.             res += 1
    
17.             for child in graph[each]:
    
18.                 dfs(child, graph, visited)
    
19.    
    
20.     return res
    
21. 
    
22. def dfs(node, graph, visited):
    
23.     if node in visited:
    
24.         return
    
25.     visited.add(node)
    
26.     for each in graph[node]:
    
27.         dfs(each, graph, visited)
    
28. 
    
29. 
    
30. if __name__ == '__main__':
    
31. 
    
32.     """
    
33.     edge1:
    
34.     1----->2--->3-->4
    
35.     ^               |
    
36.     |     8         |
    
37.     |     ^         |
    
38.     |     |         V
    
39.     9<----7<----6<--5
    
40.     """
    
41.     edges1 = [
    
42.         [1, 2],
    
43.         [2, 3],
    
44.         [3, 4],
    
45.         [4, 5],
    
46.         [5, 6],
    
47.         [6, 7],
    
48.         [7, 8],
    
49.         [7, 9],
    
50.         [9, 1],
    
51.     ]
    
52.     res1 = dag_traverse(edges1)
    
53.     assert res1 == 1
    
54.     print('*' * 40)
    
55. 
    
56.     """
    
57.     edge2:
    
58.     1----->2--->3-->4
    
59.     ^               |
    
60.     |     8         |
    
61.     |     ^         |
    
62.     |     |         V
    
63.     9<----7<----6   5
    
64.     """
    
65.     edges2 = [
    
66.         [1, 2],
    
67.         [2, 3],
    
68.         [3, 4],
    
69.         [4, 5],
    
70.         # [5, 6],
    
71.         [6, 7],
    
72.         [7, 8],
    
73.         [7, 9],
    
74.         [9, 1],
    
75.     ]
    
76.     res2 = dag_traverse(edges2)
    
77.     assert res2 == 2
    
78. 
    
79. 
    
80.     """
    
81.     edge3:
    
82.     1----->2--->3-->4
    
83.                     |
    
84.           8         |
    
85.           ^         |
    
86.           |         V
    
87.     9<----7<----6   5
    
88.     """
    
89.     edges3 = [
    
90.         [1, 2],
    
91.         [2, 3],
    
92.         [3, 4],
    
93.         [4, 5],
    
94.         # [5, 6],
    
95.         [6, 7],
    
96.         [7, 8],
    
97.         [7, 9],
    
98.         # [9, 1],
    
99.     ]
    
100.     res3 = dag_traverse(edges3)
     
101.     assert res3 == 2

复制代码

nicemayi 发表于 2019-4-9 13:22
感觉你的解法是O(n)的，带剪枝并不是爆搜:)
对于这道题看到很多人推崇scc Kosaraju 看的也是挺懵逼的， ...

hmm... 我看了一下，感觉是O(n2)的，在worst case下比如 A->B->C->D, 我们恰巧loop的顺序是从D开始，那么对于每个点我们都要作为起点开始，对于他所有可以到的点进行一次loop

原楼主给的解法是剪枝了的但是有些问题，我这好像并没有剪啊。。

另外我感觉面试的时候如果能条理清晰解释这个解法写出clean code感觉没有什么问题，如果写SCC那个，可能要求更高，包括代码量，解释量等等

ericliu03 发表于 2019-4-10 04:58
hmm... 我看了一下，感觉是O(n2)的，在worst case下比如 A->B->C->D, 我们恰巧loop的顺序是从D开始，那么 ...

对，我没想到过你给的这个case。visited我的理解就是剪枝了。

nicemayi 发表于 2019-4-10 10:28
对，我没想到过你给的这个case。visited我的理解就是剪枝了。

或者还有一种优化思路：从入度为0的点开始遍历，当然如果没有就说明有环，从任何点开始都会是O(n)的。trade off是牺牲一点空间复杂度。

nicemayi 发表于 2019-4-10 10:30
或者还有一种优化思路：从入度为0的点开始遍历，当然如果没有就说明有环，从任何点开始都会是O(n)的。tra ...

我想了想，这个肯定是要比彻底暴力要好的。比如，对于每个点都跑一遍dfs（或者bfs）找到相连的，然后一个recursion 再对没有visited的点来一遍，直到全部visit，有几层recursion就是有几个start，全部试一遍最少的就是答案。。

我觉得你说的优化确实能解决一些case，提高avg 复杂度，但是我感觉这类优化一般不能提高worst case的复杂度，比如一个情况：
1->0, 2->0, 3->0, 4->0，0->5->6->7->8，那么就是 n/2 * n/2 还是O(n2)？

感觉应该是可以用数学证明一下的，然而数学并不好0.0

nicemayi 发表于 2019-4-9 13:22
感觉你的解法是O(n)的，带剪枝并不是爆搜:)
对于这道题看到很多人推崇scc Kosaraju 看的也是挺懵逼的， ...

为什么第三个case 结果是2不是3呢？

补充内容 (2019-5-2 15:18):
如果第三个case是2的话，那么第二个case不应该是1吗？从6号出发都能访问到呀？

维护所有点的入度，对有向图run一遍dfs，遇到圈就破圈，即如果当前点已经访问过且是在圈上则将其入度减一，最后得到一个DAG，找出所有入度为0的点即可

1. #include <iostream>
   
2. #include <unordered_map>
   
3. #include <unordered_set>
   
4. #include <vector>
   
5. 
   
6. using namespace std;
   
7. 
   
8. unordered_map<int, vector<int>> g;
   
9. unordered_map<int, int> indeg, visited;
   
10. 
    
11. void dfs(int u) {
    
12.         if (visited[u] == 1) return;
    
13.         if (visited[u] == -1) {
    
14.                 --indeg[u];
    
15.                 return;
    
16.         }
    
17.         visited[u] = -1;
    
18.         for (int v : g[u]) {
    
19.                 dfs(v);
    
20.         }
    
21.         visited[u] = 1;
    
22. }
    
23. 
    
24. int solution(const vector<vector<int>> &edges) {
    
25.         unordered_set<int> nodes;
    
26.         for (const auto &e : edges) {
    
27.                 g[e[0]].push_back(e[1]);
    
28.                 ++indeg[e[1]];
    
29.                 nodes.insert(e[0]);
    
30.                 nodes.insert(e[1]);
    
31.         }
    
32.         for (int x : nodes) {
    
33.                 dfs(x);
    
34.         }
    
35.         int res = 0;
    
36.         for (int x : nodes) {
    
37.                 res += indeg[x] == 0;
    
38.         }
    
39.         return res;
    
40. }
    
41. 
    
42. int main() {
    
43.         // your code goes here
    
44.         vector<vector<int>> edges = {{1, 3}, {3, 2}, {2, 1}, {3, 4}, {2, 4}, {3, 5},
    
45.                                                                 {5, 4}, {4, 6}, {6, 4}, {7, 4}, {7, 12}, {7, 8},
    
46.                                                                 {8, 7}, {10, 9}, {11, 10}};
    
47.         cout << solution(edges) << endl;
    
48.         return 0;
    
49. }

复制代码

nicemayi 发表于 2019-4-9 00:22
感觉你的解法是O(n)的，带剪枝并不是爆搜:)
对于这道题看到很多人推崇scc Kosaraju 看的也是挺懵逼的， ...

你的算法是错的，test case #2的结果应该是1，从点6开始可以达到所有其他点