পাইথনে গ্রাফে বিশেষ ধরনের সাবগ্রাফ বের করার প্রোগ্রাম

মনে করুন একটি বিশেষ ধরনের গ্রাফ আছে যাতে দু ধরনের ভের্টেক্স আছে: হেড এবং ফিট। গ্রাফে শুধু একটি হেড থাকে এবং kটি এজ হেডকে প্রতিটি ফিটের সাথে সংযুক্ত করে। যদি আমাদের একটি অনডায়рек্টেড, আনওয়েটেড গ্রাফ দেওয়া থাকে, তবে আমাদের গ্রাফের ভার্টেক্স-ডিসজয়েন্ট সাবগ্রাফগুলোর মধ্যে এই বিশেষ ধরনের গ্রাফগুলো খুঁজে বের করতে হবে। দুটি গ্রাফ ভার্টেক্স-ডিসজয়েন্ট হয় যদি তাদের কোনো কমন ভার্টেক্স না থাকে।

যেমন, ইনপুট এমন হলে

নোড সংখ্যা (n) = 5, ফিট সংখ্যা (t) = 2 হলে, আউটপুট হবে ৫।

দেওয়া গ্রাফের ভার্টেক্স-ডিসজয়েন্ট সাবগ্রাফ হিসেবে ৫টি এমন বিশেষ গ্রাফ থাকতে পারে।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

G := n+1 সংখ্যক খালি লিস্ট ধারণকারী একটি লিস্ট
edges-এ থাকা প্রতিটি item-এর জন্য
- s := item[0], d := item[1]
- d কে G[s]-এ এবং s কে G[d]-এ অ্যাপেন্ড করুন
visit := একটি খালি ম্যাপ
i = 0 থেকে n-1 পর্যন্ত
- 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
return 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)]