पायथन में यूलर सर्किट बनाने के लिए आवश्यक न्यूनतम एज खोजें

मान लीजिए हमारे पास b नोड्स और a एज का एक अनिर्देशित ग्राफ है। हमें इस ग्राफ में यूलर सर्किट बनाने के लिए आवश्यक न्यूनतम एज ढूंढनी है।

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

तो आउटपुट 1 होगा।

समाधान दृष्टिकोण

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

dfs(g, visit, odd_vert, degree, comp, v) फ़ंक्शन परिभाषित करें:
- visit[v] := 1
- यदि degree[v] % 2 == 1, तो odd_vert[comp] := odd_vert[comp] + 1
- u को 0 से len(g[v])-1 तक के लिए:
  - यदि visit[u] == 0, तो dfs(g, visit, odd_vert, degree, comp, u)
मुख्य विधि से:
- g := [ [] for _ in range(n+1) ]
- e := [], o := []
- degree := [0] * (n + 1)
- visit := [0] * (n + 1)
- odd_vert := [0] * (n + 1)
- i को 0 से m-1 तक के लिए:
  - g[s[i]].append(d[i])
  - g[d[i]].append(s[i])
  - degree[s[i]] += 1
  - degree[d[i]] += 1
- ans := 0, comp := 0
- i को 1 से n तक के लिए:
  - यदि visit[i] == 0:
    - comp += 1
    - dfs(g, visit, odd_vert, degree, comp, i)
    - यदि odd_vert[comp] == 0, तो e.append(comp)
    - अन्यथा, o.append(comp)
- यदि len(o) == 0 और len(e) == 1, तो 0 लौटाएं।
- यदि len(o) == 0, तो len(e) लौटाएं।
- यदि len(e) != 0, तो ans += len(e)
- i को 0 से len(o)-1 तक: ans += odd_vert[i] // 2
- ans लौटाएं।

उदाहरण

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

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 i 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))

इनपुट

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