Leetcode Problem 1857. Largest Color Value in a Directed Graph

1857. Largest Color Value in a Directed Graph

Leetcode Solutions

Topological Sort Using Kahn's Algorithm

  1. Initialize n as the number of nodes, adj as the adjacency list, indegree as the array to store the number of incoming edges for each node, and count as a 2D-array to store color frequencies.
  2. Initialize a queue q and push all nodes with indegree of 0 into it.
  3. Initialize answer to 0 and nodesSeen to 0.
  4. While q is not empty, process nodes in the queue:
    • Dequeue node from q.
    • Increment the frequency of node's color in count and update answer.
    • Increment nodesSeen.
    • For each neighbor of node, update count[neighbor] and decrement indegree[neighbor].
    • If indegree[neighbor] becomes 0, enqueue neighbor.
  5. If nodesSeen is less than n, return -1 to indicate a cycle. Otherwise, return answer.
UML Thumbnail

Depth First Search with Cycle Detection

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...