মনে করুন, আমাদের একটি গ্রাফ দেওয়া আছে যাতে n ভের্টেক্স ০ থেকে n-1 পর্যন্ত নম্বর করা। গ্রাফ অনডায়রিক্টেড এবং প্রতিটি এজ-এর একটি ওজন আছে। গ্রাফে তিন ধরনের ওজন থাকতে পারে এবং প্রতিটি ওজন একটি নির্দিষ্ট টাস্ক বোঝায়। দুজন মানুষ গ্রাফ ট্রাভার্স করতে পারে: জ্যাক এবং কেসি। জ্যাক ট্রাভার্স করতে পারলে এজ ওজন ১ থাকতে হবে, কেসি ট্রাভার্স করতে পারলে ওজন ২, এবং দুজনো ট্রাভার্স করতে পারলে ওজন ৩। আমাদের গ্রাফ ট্রাভার্সেবল बनाने জন্য প্রয়োজনীয় এজ রিমুভ করতে হবে। রিমুভ করা এজ সংখ্যা রিটার্ন করুন, অথবা যদি সম্ভব না হয় তবে -1 রিটার্ন করুন।
যেমন, ইনপুট এমন হলে
এবং n = 5 হলে, আউটপুট হবে -1।
এজ রিমুভ করে গ্রাফকে দুজনের জন্যও ট্রাভার্সেবল করা সম্ভব নয়। তাই উত্তর -1।
সমাধান পদ্ধতি
এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:
find() ফাংশন ডিফাইন করুন। এটি val প্যারামিটার নেবে
যদি val != root[val] হয়, তবে
root[val] := find(root[val])
root[val] রিটার্ন করুন
union() ফাংশন ডিফাইন করুন। এটি val1, val2 প্যারামিটার নেবে
val1 := find(val1), val2 := find(val2)
যদি val1 == val2 হয়, তবে
0 রিটার্ন করুন
root[val1] := val2
1 রিটার্ন করুন
res := 0, edge1 := 0, edge2 := 0
root := 0 থেকে n+1 পর্যন্ত রেঞ্জের লিস্ট
e-এ থাকা প্রতিটি এজ (u, v) এবং এর ওজন w-এর জন্য
যদি u == 3 হয়, তবে
যদি union(v, w) নন-জিরো হয়, তবে
edge1++, edge2++
অন্যথায়, res++
root0 := root[0:] (কপি)
e-এ থাকা প্রতিটি এজ (u, v) এবং ওজন w-এর জন্য
যদি u == 1 হয়, তবে
যদি union(v, w) নন-জিরো, তবে edge1++
অন্যথায় res++
root := root0
e-এ থাকা প্রতিটি এজ (u, v) এবং ওজন w-এর জন্য
যদি u == 2 হয়, তবে
যদি union(v, w) নন-জিরো, তবে edge2++
অন্যথায় res++
যদি edge1 == edge2 == n-1 হয়, তবে res রিটার্ন করুন, অন্যথায় -1 রিটার্ন করুন
উদাহরণ
নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:
def solve(n, e): def find(val): if val != root[val]: root[val] = find(root[val]) return root[val] def union(val1, val2): val1, val2 = find(val1), find(val2) if val1 == val2: return 0 root[val1] = val2 return 1 res = edge1 = edge2 = 0 root = list(range(n + 1)) for u, v, w in e: if u == 3: if union(v, w): edge1 += 1 edge2 += 1 else: res += 1 root0 = root[:] for u, v, w in e: if u == 1: if union(v, w): edge1 += 1 else: res += 1 root = root0 for u, v, w in e: if u == 2: if union(v, w): edge2 += 1 else: res += 1 return res if edge1 == edge2 == n - 1 else -1 print(solve(5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]))
ইনপুট
Input: 5, [(0,1,1),(1,2,2),(2,3,3),(3,4,1),(4,0,2)]
আউটপুট
-1
