Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें?

डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं।

एल्गोरिदम

  • सभी नोड्स का सेट बनाएं (0 से n-1)।
  • सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं।
  • सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)।
  • यही मिनिमम वर्टेक्स सेट है।

उदाहरण कोड


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)] -> {0,2,3}

इनपुट/आउटपुट

इनपुट: [(0,1),(2,1),(3,1),(1,4),(2,4)]
आउटपुट: {0, 2, 3}

  1. Python से बाइनरी ट्री में गुड लीफ नोड पेयर्स की संख्या कैसे ढूंढें? Python से बाइनरी ट्री में गुड लीफ नोड पेयर्स की संख्या कैसे ढूंढें?

    दो लीफ नोड्स का पेयर गुड है अगर उनके बीच का सबसे छोटा पथ ≤ d है। पोस्ट-ऑर्डर DFS से सभी गुड पेयर्स काउंट करें। एल्गोरिदम रिकर्सिव util(root) रिटर्न करता है: प्रत्येक लीफ के लिए [depth_from_root, 0] (दूसरा मान अपडेट होता है)। लेफ्ट और राइट सबट्री के लीफ्स के लिए: डेप्थ्स इन्क्रीमेंट करें। सभी लेफ्ट-

  1. Python से सबट्री में समान लेबल वाले नोड्स की संख्या कैसे ढूंढें? Python से सबट्री में समान लेबल वाले नोड्स की संख्या कैसे ढूंढें?

    रूटेड ट्री में प्रत्येक नोड के लिए, उसके सबट्री में उसी लेबल वाले नोड्स की संख्या ढूंढें (लेबल्स लोअरकेस लेटर्स)। एल्गोरिदम एज लिस्ट से ग्राफ बनाएं (अनडायरेक्टेड)। लेबल मैप बनाएं। रिकर्सिव DFS r(ni): चिल्ड्रन के काउंटर्स मर्ज करें, अपना लेबल जोड़ें, R[ni] = count[label]। पैरेंट लिंक हटाकर साइकिल अव

  1. पायथन में BST में रेंज में नोड्स की संख्या खोजने का प्रोग्राम पायथन में BST में रेंज में नोड्स की संख्या खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक BST है, और हमारे पास बाएं और दाएं बाउंड l और r भी हैं, हमें रूट में उन सभी नोड्स की संख्या गिननी है जिनके मान l और r के बीच हैं (सम्मिलित)। उदाहरण के लिए, यदि इनपुट जैसा है: l = 7, r = 13, तो आउटपुट 3 होगा, क्योंकि तीन नोड्स हैं: 8, 10, 12। इसे हल करने के लिए हम निम्न चरणों