একটি এজ লিস্ট দেওয়া আছে যেখানে প্রতিটি আইটেম (u, v) মানে u হল v-এর পেরেন্ট। ট্রি-তে সবচেয়ে লম্বা পথের দৈর্ঘ্য বের করতে হবে। পথ দৈর্ঘ্য = ১ + পথে থাকা নোডের সংখ্যা।
উদাহরণ: এজ লিস্ট [(1, 2), (1, 3), (1, 4), (4, 5), (5, 7), (1, 6), (4, 8)] হলে আউটপুট 5। কারণ পথ [1, 4, 5, 7] (৪টি নোড), পথ দৈর্ঘ্য = ১ + ৪ = ৫।
সমাধানের পদ্ধতি
ট্রির ডায়ামিটার (diameter) বের করার классиক্যাল BFS/DFS পদ্ধতি:
- এডজেসেন্সি লিস্ট
gতৈরি করুন (অনডাইরেক্টেড গ্রাফ হিসেবে)। - যভাবেই একটা নোড
oথেকে BFS করে সবচেয়ে দূরতম নোডfবের করুন। fথেকে আবার BFS করে সবচেয়ে দূরতম নোড বের করুন। সেই দূরততাই ডায়ামিটার।- পথ দৈর্ঘ্য = ডায়ামিটার + ১।
পাইথন কোড
def solve(edges):
# এডজেসেন্সি লিস্ট তৈরি করুন
g = {}
for u, v in edges:
if u not in g:
g[u] = []
g[u].append(v)
if v not in g:
g[v] = []
g[v].append(u)
d = {}
def bfs(o):
d[o] = 1
f = o
q = [o]
for x in q:
for y in g[x]:
if y not in d:
d[y] = d[x] + 1
if d[y] > d[f]:
f = y
q.append(y)
return f
# যেকোনো নোড থেকে শুরু করুন (এখানে প্রথম নোড)
for o in g:
f = bfs(o)
d = {}
return d[bfs(f)]
return 0
# টেস্ট
edges = [(1, 2), (1, 3), (1, 4), (4, 5), (5, 7), (1, 6), (4, 8)]
print(solve(edges)) # আউটপুট: 5ব্যাখ্যা
প্রথম BFS-এ যেকোনো নোড থেকে সবচেয়ে দূরতম নোড f পাওয়া যায়। দ্বিতীয় BFS-এ f থেকে সবচেয়ে দূরতম নোড পাওয়া যায়, সেই দূরততাই ট্রির ডায়ামিটার।
সময় জটিলতা
O(V + E) - দুটি BFS ট্রাভার্সাল।
