Similar Problems
Similar Problems not available
Largest Color Value In A Directed Graph - Leetcode Solution
Companies:
LeetCode: Largest Color Value In A Directed Graph Leetcode Solution
Difficulty: Hard
Topics: hash-table dynamic-programming graph
The problem "Largest Color Value In A Directed Graph" on LeetCode can be solved using dynamic programming and topological sorting.
Problem Statement:
Given a directed graph, containing N nodes, and edges, each node i is assigned a color colors[i]. Find the largest number of colors in a longest path starting from the source(s) and ending at any node of the graph. (If a cycle is detected, return -1.)
Solution:
Step 1: Topological Sorting
The problem requires finding the longest path in the directed graph starting from the source(s). To achieve this, we can use topological sorting. If a directed graph has cycles, then it cannot be topologically sorted, which means that there is no longest path. Therefore, we need to check if the graph contains any cycle or not.
Step 2: Detecting Cycles
To check if a graph contains cycles, we can use Depth First Search (DFS) algorithm, to traverse the graph and maintain a visited array and a recursion stack. The visited array keeps track of all the nodes that have been visited during the DFS traversal, and the recursion stack is used to detect cycles.
We start by selecting a node as the source and calling DFS on it. If during the DFS traversal, we visit a node that is already present in the recursion stack, then it is a cycle, and we return -1.
Step 3: Dynamic Programming
Once we have checked for cycles and topologically sorted the graph, we can start optimizing the solution using dynamic programming. We can use an array, colorCount, to keep track of the maximum count of colors seen so far for each node in the topological order.
For each node, we iterate over its outgoing edges, and for each edge, we update the colorCount of the destination node by taking the maximum between the colorCount of the current node and the colorCount of the destination node plus 1, if the color of the destination node is not already visited.
Finally, we return the maximum value in the colorCount array as the answer.
Pseudo Code:
def largestPathColors(graph: List[List[int]], colors: str) -> int:
n = len(colors)
# Step 1: Topological Sorting
queue, indegree = [], [0] * n
for u in range(n):
for v in graph[u]:
indegree[v] += 1
for u in range(n):
if indegree[u] == 0:
queue.append(u)
# Step 2: Detecting Cycles
visited, stack = set(), set()
def hasCycle(u):
if u in visited:
return False # Already visited node
visited.add(u)
stack.add(u)
for v in graph[u]:
if v in stack or hasCycle(v):
return True # Cycle detected
stack.remove(u)
return False
while queue:
u = queue.pop(0)
if hasCycle(u):
return -1
# Step 3: Dynamic Programming
colorCount = [0] * n
colorCount[u] = 1
for v in graph[u]:
for i in range(26):
if ord(colors[v]) == (i + 97):
colorCount[v] = max(colorCount[v], colorCount[u] + (i == ord(colors[v]) - 97))
break
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return max(colorCount)
Time Complexity:
The time complexity of the above solution is O(N + M), where N is the number of nodes and M is the number of edges in the graph. The cost of topological sorting is O(N + M), and the cost of detecting cycles using DFS is O(N + M). The cost of dynamic programming is also O(N + M) as we visit every edge exactly once.
Space Complexity:
The space complexity of the above solution is O(N) to store the visited set, recursion stack, queue, and colorCount array.
Largest Color Value In A Directed Graph Solution Code
1