मान लीजिए हमारे पास एक निर्देशित ग्राफ की एज सूची है, इसमें n नोड हैं और नोड नाम 0 से n-1 हैं। हमारे पास दो पूर्णांक मान a और b भी हैं। हमें जांचना है कि क्या कोई नोड c ऐसा है कि हम c से a जा सकते हैं और c से b भी जा सकते हैं।
इसलिए, यदि इनपुट ग्राफ छवि में दिखाए अनुसार है और a = 2, b = 3, तो आउटपुट होगा True, क्योंकि यहां c = 0, इसलिए 0 से 2 और 0 से 3 तक मार्ग है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
DFS()फ़ंक्शन परिभाषित करें। यहgraph, node, visitedलेगा:- यदि
nodeविज़िट नहीं किया गया है, तो:nodeको विज़िट किया गया चिह्नित करेंgraph[node]में प्रत्येकxके लिए, करें:DFS(graph, x, visited)
- यदि
- मुख्य विधि से, निम्नलिखित करें:
graph :=edge_listसे एडजेंसी सूची उत्पन्न करेंvisited_a, visited_b :=दो खाली सेटDFS(graph, a, visited_a)DFS(graph, b, visited_b)ans :=visited_bऔरvisited_aके इंटरसेक्शन से एक नई सूची- यदि
ansखाली नहीं है, तो:Trueलौटाएं
Falseलौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def edge_list_to_graph(edges):
s = set()
for x, y in edges:
s.add(x)
s.add(y)
s = len(list(s))
graph = [[] for x in range(s)]
for x, y in edges:
graph[y].append(x)
return graph
def DFS(graph, node, visited):
if node not in visited:
visited.add(node)
for x in graph[node]:
DFS(graph, x, visited)
def solve(edges, a, b):
graph = edge_list_to_graph(edges)
visited_a, visited_b = set(), set()
DFS(graph, a, visited_a)
DFS(graph, b, visited_b)
ans = list(visited_a.intersection(visited_b))
if ans:
return True
return False
ed_list = [(0, 4), (4, 3), (1, 2), (0, 1), (0, 2), (1, 1)]
a = 2
b = 3
print(solve(ed_list, a, b))
इनपुट
[(0, 4), (4, 3), (1, 2), (0, 1), (0, 2), (1, 1)], 2, 3
आउटपुट
True