সমস্যা বিবরণ
sticks লিস্টে প্রতিটি এলিমেন্ট [end1, end2] আকারে একটি স্টিক রিপ্রেজেন্ট করে (এন্ড ভ্যালু ১-৬)। দুটি স্টিক কানেক্ট করা যায় যদি তাদের কোনো একটা এন্ড মিলে যায়। কানেক্ট করার পর নया স্টিকের এন্ড গুলো হবে বাকি দুটি এন্ড। সর্বোচ্চ দৈর্ঘ্যের স্টিক বের করতে হবে।
উদাহরণ
sticks = [[2, 3], [2, 4], [3, 5], [6, 6]]
কানেকশন:
[2,3] + [2,4] → [3,4] (length 2)
[3,4] + [3,5] → [4,5] (length 3)
[6,6] আলাদা (length 1)
Output: 3
মডেলিং: গ্রাফ প্রობ্লেম
- ভার্টেক্স = এন্ড ভ্যালু (১-৬)
- এজ = স্টিক (দুই ভার্টেক্স কানেক্ট করে)
- প্রশ্ন: গ্রাফে সর্বোচ্চ লেন্থের সিম্পল পাথ (Simple Path) কত? (এজ রিপিট নেই)
অ্যালগরিদম: DFS + ব্যাকট্র্যাকিং (স্মল গ্রাফ)
ভার্টেক্স সংখ্যা ছোট (১-৬), তাই সব ভার্টেক্স থেকে DFS চালিয়ে সর্বোচ্চ পাথ বের করা যায়।
পাইথন কোড
from collections import defaultdict
class Solution:
def solve(self, sticks):
def dfs(node, edge_idx, visited):
if edge_idx is not None:
if edge_idx in visited:
return 0
visited.add(edge_idx)
max_len = 0
for e_idx in graph[node]:
# অন্য এন্ড বের করুন
u, v = sticks[e_idx]
next_node = v if u == node else u
max_len = max(max_len, 1 + dfs(next_node, e_idx, visited))
if edge_idx is not None:
visited.remove(edge_idx)
return max_len
# গ্রাফ বানান
sticks = [(s[0], s[1]) for s in sticks]
vertices = set()
graph = defaultdict(set)
for i, (u, v) in enumerate(sticks):
graph[u].add(i)
graph[v].add(i)
vertices.add(u)
vertices.add(v)
# সব ভার্টেক্স থেকে DFS
max_result = 0
for v in vertices:
max_result = max(max_result, dfs(v, None, set()))
return max_result - 1 if max_result > 0 else 0 # এজ কাউন্ট = নোড কাউন্ট - ১
ob = Solution()
sticks = [[2, 3], [2, 4], [3, 5], [6, 6]]
print(ob.solve(sticks)) # 3
লজিক ব্যাখ্যা
dfsরিটার্ন করে নোড কাউন্ট (এজ কাউন্ট + ১)visitedসেটে এজ ইনডেক্স রাখা হয় যাতে একই এজ دوبার ইউজ না হয়max_result - 1= এজ সংখ্যা = স্টিক দৈর্ঘ্য
জটিলতা বিশ্লেষণ
- সময় জটিলতা: O(V × E!) ওয়ার্স্ট কেস, কিন্তু V ≤ ৬ (এন্ড ১-৬) এখানে, তাই ফাস্ট
- স্থান জটিলতা: O(E) — রিকার্শন স্ট্যাক + ভিজিটেড সেট
- বড় গ্রাফের জন্য NP-Hard (Longest Path Problem)
উপসংহার
- স্টিক কানেকশন = গ্রাফে পাথ ফাইন্ডিং
- স্মল ডোমেইন (১-৬) → ব্রুট ফোর্স DFS কাজ করে
- এজ ভিজিটেড ট্র্যাকিং এজ রি-ইউজ প্রতিরোধ করে
- বাস্তবে: ডোমিনো চেইন, পাইপ কানেকশন, নেটওয়ার্ক রাউটিং
