পাইথনে অয়লার সার্কিট बनाने জন্য ন্যূনতম এজ যোগ করুন

সমস্যা বিবরণ

একটি অনির্দেশিত গ্রাফ দেওয়া আছে যার নোড সংখ্যা b এবং এজ সংখ্যা a। এতে অয়লার সার্কিট (Euler Circuit) তৈরি করার জন্য ন্যূনতম কতগুলো এজ যোগ করতে হবে তা বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট গ্রাফ নিচের চিত্রের মতো হলে আউটপুট হবে 1।

সমাধানের ধাপসমূহ

dfs(g, visit, odd_vert, degree, comp, v) ফাংশন লিখুন:
- visit[v] = 1।
- যদি degree[v] % 2 == 1 হয়, odd_vert[comp]++।
- প্রতিটি প্রতিবেশী u এর জন্য যদি visit[u] == 0 হয়, রিকার্সিভলি ডিএফএস কল করুন।
মূল পদ্ধতিতে:
- এডজেসেন্সি লিস্ট g, ডিগ্রি অ্যারে, ভিজিট অ্যারে, odd_vert অ্যারে তৈরি করুন।
- প্রতিটি এজ যোগ করুন এবং ডিগ্রি আপডেট করুন।
- প্রতিটি কম্পোনেন্টের জন্য ডিএফএস চালান। বিজোড় ডিগ্রি वाले নোড সংখ্যা odd_vert[comp] তে স্টোর করুন।
- কম্পোনেন্টগুলোকে দুই শ্রেণিতে ভাগ করুন: যাদের বিজোড় ডিগ্রি ০ (ইভেন কম্পোনেন্ট) এবং যাদের বিজোড় ডিগ্রি > ০ (অড কম্পোনেন্ট)।
- ফলাফল হিসাব করুন:
  - যদি কোনো অড কম্পোনেন্ট না থাকে এবং শুধু একটি ইভেন কম্পোনেন্ট থাকে, রিটার্ন ০।
  - যদি কোনো অড কম্পোনেন্ট না থাকে, রিটার্ন ইভেন কম্পোনেন্টের সংখ্যা।
  - অন্যথায়, আউটপুট = ইভেন কম্পোনেন্টের সংখ্যা + Σ(অড কম্পোনেন্টের বিজোড় ডিগ্রি সংখ্যা / ২)।

পাইথন কোড উদাহরণ

def dfs(g, visit, odd_vert, degree, comp, v):
    visit[v] = 1
    if degree[v] % 2 == 1:
        odd_vert[comp] += 1
    for u in range(len(g[v])):
        if visit[u] == 0:
            dfs(g, visit, odd_vert, degree, comp, u)

def solve(n, m, s, d):
    g = [[] for _ in range(n + 1)]
    e = []
    o = []
    degree = [0] * (n + 1)
    visit = [0] * (n + 1)
    odd_vert = [0] * (n + 1)
    for i in range(m):
        g[s[i]].append(d[i])
        g[d[i]].append(s[i])
        degree[s[i]] += 1
        degree[d[i]] += 1
    ans = 0
    comp = 0
    for i in range(1, n + 1):
        if visit[i] == 0:
            comp += 1
            dfs(g, visit, odd_vert, degree, comp, i)
            if odd_vert[comp] == 0:
                e.append(comp)
            else:
                o.append(comp)
    if len(o) == 0 and len(e) == 1:
        return 0
    if len(o) == 0:
        return len(e)
    if len(e) != 0:
        ans += len(e)
    for i in range(len(o)):
        ans += odd_vert[i] // 2
    return ans

b = 3
a = 2
source = [1, 2]
destination = [2, 3]
print(solve(b, a, source, destination))  # আউটপুট: 1

ইনপুট

b = 3 a = 2 source = [ 1, 2 ] destination = [ 2, 3]