একটি ডাইরেক্টেড গ্রাফে দুটি নোড a এবং b দেওয়া আছে। যেকোনো নোড c আছে কিনা যেন c → a এবং c → b পথ উভয়ই বিদ্যমান থাকে।
ইনপুট উদাহরণ
edges = [(0,4),(4,3),(1,2),(0,1),(0,2),(1,1)]
a = 2, b = 3আউটপুট: True (c = 0 যেহেতু 0→2 এবং 0→3 পথ আছে)
অ্যালগরিদম
- এজ লিস্ট থেকে রিভার্স অ্যাকজেসেন্সি লিস্ট বানান (কারণ u→v মানে v থেকে u-তে যাওয়া যায়)।
aএবংb-থেকে আলাদা আলাদা DFS চালিয়ে রিচেয়achable নোড সেট বানান।- দুই সেটের ইন্টারসেকশন খালি নয় কিনা চেক করুন।
পাইথন কোড
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 _ 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))
return True if ans else False
# টেস্ট
ed_list = [(0,4),(4,3),(1,2),(0,1),(0,2),(1,1)]
print(solve(ed_list, 2, 3)) # Trueব্যাখ্যা
রিভার্স গ্রাফে DFS করলে সোর্স থেকে যেসব নোডে যেতে পারে সেগুলো আসলে সেসব নোড থেকে সোর্সে যাওয়া যায়। ইন্টারসেকশন দিয়ে কমন প্যারেন্ট বের করা হয়।
