पायथन का उपयोग करके सभी नोड्स तक पहुंचने के लिए न्यूनतम संख्या में कोने खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक निर्देशित चक्रीय ग्राफ है, जिसमें n कोने हैं और नोड्स 0 से n-1 तक गिने जाते हैं, ग्राफ को किनारे की सूची द्वारा दर्शाया जाता है, जहां किनारों [i] =(यू, वी) नोड यू से एक निर्देशित किनारे का प्रतिनिधित्व करता है। नोड वी। हमें शिखर का सबसे छोटा सेट ढूंढना है जिससे ग्राफ में सभी नोड्स पहुंच योग्य हैं। (हम किसी भी क्रम में शिखर वापस कर सकते हैं)।

तो, अगर इनपुट पसंद है

तब आउटपुट [0,2,3] होगा क्योंकि ये दोनों कोने किसी भी अन्य कोने से उपलब्ध नहीं हैं, इसलिए यदि हम उनसे शुरू करते हैं तो हम सभी को कवर कर सकते हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=किनारों का आकार

• all_nodes :=0 से n तक का एक नया सेट

• v :=एक नया सेट

• किनारों में प्रत्येक किनारे (i, j) के लिए, करें

  • j को v में जोड़ें

• उत्तर:=सभी नोड्स से सभी सामान्य किनारों को हटा दें और सभी_नोड्स से वी को हटा दें

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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}