股沟店面过经，过了也然并卵

想問樓主那個 graph 有沒有方向性阿？

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

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

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

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

首先用adj map先画图，然后 must_succeed(node) 就是对于每一个点都尝试作为起点进行DFS，在DFS的过程中如果有环（有向图DFS找环就是lc210），直接返回false。如果没有环，走到了一个点，这个点已经是leaf node，看一下这个点 is_success(node)，不是success的话返回false，是的话继续DFS直到遍历完整张图，这时可以返回true。

祝楼主后续一切顺利

1. public boolean must_succeed(int node){
   
2.         return dfs(node, new HashSet<Integer>());
   
3. }
   
4. 
   
5. private boolean dfs(int node, Set<Integer> visited){
   
6.         if(visited.contains(node)) return false; //cycle detected
   
7.         if(!adj.containsKey(node)){ //if leaf node
   
8.         return success_node(node);
   
9. }
   
10. 
    
11.         visited.add(node);
    
12.         for(int next : adj.get(node)){
    
13. if(!dfs(next, visited))) return false;
    
14. }
    
15. visited.remove(node);
    
16. return true;
    
17. }
    

复制代码

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

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

reverse pointing direction between nodes and use bfs, topological sorting?

Eventual safe state 原题改编

抱抱楼主，楼主你的麻面得怎么样