पायथन में दिए गए ग्राफ में विशेष प्रकार के सबग्राफ खोजने का कार्यक्रम

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

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

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

ऐसे 5 विशेष ग्राफ़ हो सकते हैं जो दिए गए ग्राफ़ के शीर्ष असंबद्ध उप-अनुच्छेद हैं।

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

G :=एक नई सूची जिसमें n+1 खाली सूचियां हैं
किनारों में प्रत्येक आइटम के लिए, करें
- s :=आइटम[0]
- d :=आइटम[1]
- G[s] के अंत में d डालें
- जी के अंत में डालें[डी]
विजिट :=एक नया नक्शा
मैं के लिए 0 से n की सीमा में, करते हैं
- v :=जी[i]
- यदि v का आकार 1 के समान है, तो
  - s :=v[0]
  - यदि विज़िट में उपस्थित नहीं हैं, तो
    - विजिट[s] :=[i]
  - अन्यथा,
    - विज़िट के अंत में मुझे संलग्न करें[s]
- अन्यथा जब v का आकार 0 के समान हो, तो
  - n :=n - 1
tmp :=0
विज़िट में प्रत्येक k के लिए, करें
- x :=विज़िट का आकार[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)]