मान लीजिए हमारे पास एक डायरेक्टेड एसाइक्लिक ग्राफ (DAG) है जिसे एडजेसेंसी लिस्ट द्वारा दर्शाया गया है। हमें ग्राफ में बिना नोड दोहराव के सबसे लंबे पथ को ढूंढना है।
उदाहरण के लिए, यदि इनपुट ग्राफ है:
तो आउटपुट 4 होगा, क्योंकि पथ 0 → 1 → 3 → 4 → 2 है जिसकी लंबाई 4 है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम DFS + मेमोइजेशन (DP) का उपयोग करेंगे:
- ans := 0
- n := ग्राफ में नोड्स की संख्या
- table := आकार n की लिस्ट, -1 से भरी हुई
- dfs(u) फंक्शन परिभाषित करें:
- यदि table[u] != -1 है, तो table[u] लौटाएं
- p_len := 0
- graph[u] के प्रत्येक वर्टेक्स v के लिए:
- p_len := max(p_len, 1 + dfs(v))
- table[u] := p_len
- p_len लौटाएं
- मुख्य मेथड में, प्रत्येक i के लिए 0 से n-1 तक:
- ans := max(ans, dfs(i))
- ans लौटाएं
पायथन कार्यान्वयन
class Solution:
def solve(self, graph):
ans = 0
n = len(graph)
table = [-1] * n
def dfs(u):
if table[u] != -1:
return table[u]
p_len = 0
for v in graph[u]:
p_len = max(p_len, 1 + dfs(v))
table[u] = p_len
return p_len
for i in range(n):
ans = max(ans, dfs(i))
return ans
ob = Solution()
graph = [
[1, 2],
[3, 4],
[],
[4],
[2],
]
print(ob.solve(graph))इनपुट
graph = [[1, 2],[3, 4],[],[4],[2]]
आउटपुट
4
