Terminal Nodes for Each Source
Problem statement
You are given a list of directed edges. Each edges[i] = [from, to] is an edge from node from to node to. Nodes are named by strings, and every node appears in at least one edge. The edges have no cycle.
A source is a node with no incoming edge. A terminal node is a node with no outgoing edge.
For each source, find every terminal node it can reach by following one or more edges. Return one row per source: the source's name first, then the names of its terminal nodes.
- List each terminal node once in a row, even when several paths reach it.
- Sort the rows by source name, and sort the terminal names inside each row. Use plain dictionary order, so
"AB"comes before"B".
Function
sourceTerminals(edges: String[][]) → String[][]Examples
Example 1
edges = [["A","B"],["B","C"],["A","D"],["E","F"]]return = [["A","C","D"],["E","F"]]A is the only start of the first group: A goes to B and then C, and A also goes straight to D. C and D have no outgoing edge, so they are the terminal nodes for A. E reaches only F.
Example 2
edges = [["P","Q"],["P","R"],["Q","S"],["R","S"],["T","R"],["R","U"]]return = [["P","S","U"],["T","S","U"]]P and T have no incoming edge, so they are the sources. P reaches S through Q and again through R, but S is listed once. Both sources also reach U through R. Q and R have outgoing edges, so they are not terminal nodes.
Example 3
edges = [["HOME","WORK"],["GYM","HOME"],["GYM","PARK"],["CAFE","PARK"]]return = [["CAFE","PARK"],["GYM","PARK","WORK"]]The sources are CAFE and GYM; HOME has an incoming edge from GYM. GYM reaches WORK through HOME and reaches PARK directly. CAFE reaches PARK. Rows are sorted by source name, so CAFE comes before GYM.
Constraints
1 <= edges.length <= 1000edges[i].length == 2- Each name has 1 to 5 capital letters from
AtoZ. edges[i][0] != edges[i][1], and no edge appears twice.- The edges have no cycle.