पायथन में दिए गए ग्राफ में विशेष प्रकार के उपग्राफ ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक विशेष प्रकार का ग्राफ है जिसमें दो प्रकार के शीर्ष हैं जिन्हें हेड और फीट कहा जाता है। ग्राफ में केवल एक हेड होता है और k किनारे होते हैं जो हेड को प्रत्येक फीट से जोड़ते हैं। इसलिए, यदि हमें एक अनिर्देशित, अनभारित ग्राफ दिया जाता है; तो हमें ग्राफ के शीर्ष-असंयुक्त उपग्राफ में इन विशेष प्रकार के ग्राफ को ढूंढना होगा। किन्हीं दो ग्राफ को शीर्ष-असंयुक्त कहा जाता है यदि उनका कोई शीर्ष समान नहीं होता।

इसलिए, यदि इनपुट इस तरह है

नोड्स की संख्या (n) = 5, फीट की संख्या (t) = 2, तो आउटपुट 5 होगा।

दिए गए ग्राफ के शीर्ष-असंयुक्त उपग्राफ के रूप में 5 ऐसे विशेष ग्राफ हो सकते हैं।

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

G := n+1 खाली सूचियों वाली एक नई सूची
edges में प्रत्येक item के लिए, करें
- s := item[0]
- d := item[1]
- d को G[s] के अंत में डालें
- s को G[d] के अंत में डालें
visit := एक नया मैप
i को 0 से n तक के लिए, करें
- v := G[i]
- यदि v का आकार 1 के समान है, तो
  - s := v[0]
  - यदि s visit में मौजूद नहीं है, तो
    - visit[s] := [i]
  - अन्यथा,
    - i को visit[s] के अंत में जोड़ें
- अन्यथा जब v का आकार 0 के समान है, तो
  - n := n - 1
tmp := 0
visit में प्रत्येक k के लिए, करें
- x := visit[k] का आकार - t
- यदि x > 0, तो
  - tmp := tmp + x
n - tmp वापस करें

उदाहरण

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

def solve(n, t, edges):
    G = [[] for _ in range(n + 1)]
    for item in edges:
        s, d = map(int, item)
        G[s].append(d)
        G[d].append(s)
    visit = {}
    for i in range(n):
        v = G[i]
        if len(v) == 1:
            s = v[0]
            if s not in visit:
                visit[s] = [i]
            else:
                visit[s].append(i)
        elif len(v) == 0:
            n -= 1
    tmp = 0
    for k in visit:
        x = len(visit[k]) - t
        if x > 0:
            tmp += x
    return n - tmp

print(solve(6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]))

इनपुट

6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]