Find Vertices from Which Every Walk Terminates

Quick Overview

Find Vertices from Which Every Walk Terminates. In the directed graph, a terminal vertex has no outgoing edges.

Find Vertices from Which Every Walk Terminates

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Other

### Problem In the directed graph, a terminal vertex has no outgoing edges. A vertex is safe when every path starting there eventually terminates instead of remaining in a cycle. Return every safe vertex label in increasing order. Self-loops are allowed. ```cpp class Solution { public: vector<int> eventualSafeNodes(vector<vector<int>>& graph); }; ``` ### Examples **Example 1:** ```text graph = [[1],[2],[],[3]] Output: [0,1,2] Explanation: The first chain terminates at2; vertex3 has a self-loop. ``` **Example 2:** ```text graph = [[1],[0],[]] Output: [2] Explanation: Vertices0 and1 form a cycle, while2 is terminal. ``` ### Constraints - Vertex count is 1 through 10000, with labels 0 through V-1. - Each neighbor list has 0 through V entries in strictly increasing order. - All labels are valid; self-loops may occur. - Total directed edge count is 1 through 40000. ### Contract considerations Return all safe labels in ascending order. ```hint Read the boundary condition When have all of a vertex's possible next steps been proved safe? ``` ### Boundary reminders Return all safe labels in ascending order.

Overview: Find Vertices from Which Every Walk Terminates. In the directed graph, a terminal vertex has no outgoing edges.

Amazon logo
Amazon
Jun 28, 2026
mediumSoftware EngineerOtherCoding & Algorithms
0
0

Problem

In the directed graph, a terminal vertex has no outgoing edges. A vertex is safe when every path starting there eventually terminates instead of remaining in a cycle. Return every safe vertex label in increasing order. Self-loops are allowed.

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph);
};

Examples

Example 1:

graph = [[1],[2],[],[3]]
Output: [0,1,2]
Explanation: The first chain terminates at2; vertex3 has a self-loop.

Example 2:

graph = [[1],[0],[]]
Output: [2]
Explanation: Vertices0 and1 form a cycle, while2 is terminal.

Constraints

  • Vertex count is 1 through 10000, with labels 0 through V-1.
  • Each neighbor list has 0 through V entries in strictly increasing order.
  • All labels are valid; self-loops may occur.
  • Total directed edge count is 1 through 40000.

Contract considerations

Return all safe labels in ascending order.

Boundary reminders

Return all safe labels in ascending order.