Leetcode Problem 2876. Count Visited Nodes in a Directed Graph

2876. Count Visited Nodes in a Directed Graph

Leetcode Solutions

Topological Sort and Cycle Detection

  1. Initialize an array indegree to keep track of the indegree of each node.
  2. Initialize a visited array to mark nodes that have been visited.
  3. Initialize a queue q and a stack s to process nodes.
  4. Fill the indegree array by counting the number of incoming edges for each node.
  5. Add nodes with indegree of 0 to the queue q.
  6. Perform a modified topological sort: a. Process nodes from the queue, marking them as visited and reducing the indegree of their neighbors. b. If a neighbor's indegree becomes 0, add it to the queue. c. Push processed nodes onto the stack s.
  7. After the queue is empty, nodes left unvisited are part of cycles. Calculate the cycle size for these nodes.
  8. Process the stack s to calculate the number of nodes visited for nodes not in cycles.
  9. Return the result array containing the number of different nodes visited for each starting node.
UML Thumbnail

DFS Traversal with Cycle Detection

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...