পাইথনে এজ দৈর্ঘ্য সীমাবদ্ধ পথের অস্তিত্ব যাচাই করার প্রোগ্রাম

আমাদের একটি আনডিরেক্টেড ওয়েটেড গ্রাফ আছে n নোড দিয়ে edgeList ব্যবহার করে, যেখানে edgeList[i]-তে তিনটি প্যারামিটার (u, v, w) থাকে যেটি নির্দেশ করে u থেকে v-এ একটি পথ আছে যার দূরত্ব w। আমাদের আরও একটি কোয়ারী অ্যারে আছে queries যেখানে queries[i]-তে (p, q, lim) থাকে। এই কোয়ারীটি জানতে চায় p থেকে q-এ একটি পথ (ডিরেক্ট বা অন্য নোড দিয়ে) আছে কিনা যার দূরত্ব lim-এর চেয়ে কম। আমাদের প্রতিটি কোয়ারীর জন্য True/False রেজাল্ট ধারণকারী একটি অ্যারে রিটার্ন করতে হবে।

উদাহরণস্বরূপ, গ্রাফ এবং কোয়ারী দেওয়া থাকলে আউটপুট হবে [True, False, True]। কারণ ১ থেকে ৪ যেতে পারি ১→৩→৪ পথ দিয়ে খরচ ১১, দ্বিতীয়টি false কারণ ২ থেকে ৩ যেতে পারি না ৩-এর চেয়ে কম খরচে, এবং তৃতীয়টি true কারণ ১ থেকে ২ যেতে পারি ১→৩→২ পথ দিয়ে খরচ ১৪ যা ১৫-এর চেয়ে কম।

সমাধানের ধাপসমূহ (ইউনিয়ন-ফাইন্ড + অফলাইন কোয়ারী)

• parent := 0 থেকে n পর্যন্ত লিস্ট

• rank := n+1 আকারের লিস্ট ০ দিয়ে ফিল করে

• find(parent, x) ফাংশন ডিফাইন করুন:

  • যদি parent[x] == x হয়, তবে x রিটার্ন করুন

  • parent[x] := find(parent, parent[x])

  • parent[x] রিটার্ন করুন

• union(parent, a, b) ফাংশন ডিফাইন করুন:

  • a := find(parent, a), b := find(parent, b)

  • যদি a == b হয়, তবে রিটার্ন করুন

  • যদি rank[a] < rank[b] হয়, তবে parent[a] := b

  • অন্যথায়, যদি rank[a] > rank[b] হয়, তবে parent[b] := a

  • অন্যথায়: parent[b] := a, rank[a] += 1

• মূল মেথড থেকে:

• edgeList-কে ওয়েট অনুযায়ী সর্ট করুন

• res := কোয়ারী সংখ্যা আকারের অ্যারে ০ দিয়ে ফিল করে

• queries := (i, ch) জোড়া লিস্ট প্রতিটি ইন্ডেক্স i এবং ভ্যালু ch এর জন্য

• queries-কে লিমিট অনুযায়ী সর্ট করুন

• ind := 0

• queries-এর প্রতিটি ইন্ডেক্স i এবং ট্রিপলেট (a, b, w) এর জন্য:

  • ind < len(edgeList) এবং edgeList[ind][2] < w থাকাকালীন:

    • union(parent, edgeList[ind][0], edgeList[ind][1])

    • ind += 1

  • res[i] := find(parent, a) == find(parent, b)

• res রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(n, edgeList, queries):
    parent = [i for i in range(n+1)]
    rank = [0 for i in range(n+1)]
    def find(parent, x):
        if parent[x] == x:
            return x
        parent[x] = find(parent, parent[x])
        return parent[x]
    def union(parent, a, b):
        a = find(parent, a)
        b = find(parent, b)
        if a == b:
            return
        if rank[a] < rank[b]:
            parent[a] = b
        elif rank[a] > rank[b]:
            parent[b] = a
        else:
            parent[b] = a
            rank[a] += 1
    edgeList.sort(key=lambda x: x[2])
    res = [0] * len(queries)
    queries = [[i, ch] for i, ch in enumerate(queries)]
    queries.sort(key=lambda x: x[1][2])
    ind = 0
    for i, (a, b, w) in queries:
        while ind < len(edgeList) and edgeList[ind][2] < w:
            union(parent, edgeList[ind][0], edgeList[ind][1])
            ind += 1
        res[i] = find(parent, a) == find(parent, b)
    return res

n = 4
edgeList = [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)]
queries = [(1,4,12),(2,3,3),(1,2,15)]
print(solve(n, edgeList, queries))

ইনপুট

4, [(1,2,16),(1,3,8),(2,4,3),(2,3,6),(4,3,3)], [(1,4,12),(2,3,3),(1,2,15)]

আউটপুট

[True, False, True]