মান লাগিয়ে, আমাদের একটি ডায়রেক্টেড এসাইক্লিক গ্রাফ আছে, n ভার্টেক্স সহ যেখানে নোডগুলো 0 থেকে n-1 পর্যন্ত নম্বর দিয়ে আছে। গ্রাফটি একটি এজ লিস্ট দিয়ে রিপ্রেজেন্ট করা আছে, যেখানে edges[i] = (u, v) মানে u থেকে v-তে একটি ডায়রেক্টেড এজ। আমাদের সবচেয়ে ছোট ভার্টেক্স সেট বের করতে হবে যেখান থেকে গ্রাফের সব নোডে পৌঁছানো সম্ভব। (ভার্টেক্সগুলো যেকোনো ক্রমে রিটার্ন করা যাবে)।
যেমন, ইনপুট যদি এমন হয়:
তবে আউটপুট হবে [0,2,3] কারণ এই দুটি ভার্টেক্স অন্য কোনো ভার্টেক্স থেকে পৌঁছানো যাবে না, তাই এখান থেকে শুরু করলে সব কভার হবে।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:
- n := edges-এর আকার
- all_nodes := 0 থেকে n-1 পর্যন্ত রেঞ্জ থেকে একটি নতুন সেট
- v := একটি নতুন সেট
- edges-এ থাকা প্রতিটি edge (i, j) জন্য:
- j v-তে যোগ করুন
- ans := all_nodes থেকে v-এর কমন এলিমেন্টগুলো বাদ দিয়ে all_nodes
- ans রিটার্ন করুন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশন দেখুন:
উদাহরণ
def solve(edges):
n = len(edges)
all_nodes = set(range(n))
v = set()
for edge in edges:
v.add(edge[1])
ans = all_nodes - v
return ans
edges = [(0,1),(2,1),(3,1),(1,4),(2,4)]
print(solve(edges))
ইনপুট
[(0,1),(2,1),(3,1),(1,4),(2,4)]
আউটপুট
{0, 2, 3}
