Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-07-12 23:59:31
https://leetcode.com/problems/find-eventual-safe-states/description/
802. Find Eventual Safe States
给你一个编号为 0 到 n-1 的有向图 graph,定义:
终端节点:没有任何向外的边。
安全节点:所有存在的路径都通向终端节点。
找出图中的所有安全节点编号,并依照编号顺序排列。
Example 1:
https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/17/picture1.png
Illustration of graph
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either
of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.
Example 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to
node 4.
思路:
1.先找出所有出度为0的节点标记为安全节点。
2.对每个点进行DFS,如果每个路径都是安全节点则该点也为安全节点,否则该点为
不安全节点,另外遇到任何cycle时该点也为不安全节点。
3.nodeState = 1 表示安全节点 nodeState = -1 表示不安全 nodeState = 0 表示未
统计的节点。
4.把节点都跑过之后,把nodeState = 1 的照顺序转成 List 即可。
Java Code:
作者: Che31128 (justjoke)   2023-07-13 00:05:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com