मान लीजिए हमारे पास एक ग्राफ है, जिसे किनारों की सूची के रूप में दर्शाया गया है। हमें जांचना है कि क्या ग्राफ ट्री का संग्रह (फॉरेस्ट) है या नहीं।
उदाहरण के लिए, यदि इनपुट निम्न ग्राफ है:
तो आउटपुट True होगा।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (DFS साइकिल डिटेक्शन):
dfs(node, prev)फ़ंक्शन परिभाषित करें।यदि
node in seen, तोFalseलौटाएं (साइकिल मिली)।seen.add(node)।प्रत्येक आसन्न नोड
nके लिएe[node]में:यदि
n != prev:यदि
dfs(n, node)गलत है, तोFalseलौटाएं।
Trueलौटाएं।मुख्य विधि से:
e := डिफॉल्टडिक्ट(list)।प्रत्येक किनारे
(u, v)के लिए:e[u].append(v);e[v].append(u)।seen := set()।प्रत्येक
nodeके लिएeमें:यदि
node not in seenऔरdfs(node, -1)गलत है, तोFalseलौटाएं।
Trueलौटाएं।
उदाहरण
from collections import defaultdict class Solution: def solve(self, edges): e = defaultdict(list) for t,f in edges: e[t].append(f) e[f].append(t) seen = set() def dfs(node, prev): if node in seen: return False seen.add(node) for adj in e[node]: if adj != prev: if not dfs(adj, node): return False return True for node in e: if node not in seen and not dfs(node, -1): return False return True ob = Solution() edges = [[0, 1],[0, 2],[4, 3]] print(ob.solve(edges))
इनपुट
[[0, 1],[0, 2],[4, 3]]
आउटपुट
True
