在 Python 中创建欧拉回路所需添加的最小边数

假设我们有一个无向图，该图包含 b 个节点和 a 条边；我们必须在此图中找到构建欧拉回路所需的最小边数。

因此，如果输入如下

则输出为 1。

为了解决这个问题，我们将遵循以下步骤 −

• 定义一个函数 dfs() 。这将需要 g、visit、odd_vert、degree、comp、v
• visit[v] := 1
• 如果 degree[v] mod 2 与 1 相同，则
  • odd_vert[comp] := odd_vert[comp] + 1
• 对于 0 到 g[v] 大小范围内的 u，执行
  • 如果 visit[u] 与 0 相同，则
    • dfs(g, visit, odd_vert, degree, comp, u)
• 从主方法执行以下操作 −
• g := n+1 个空白列表的列表
• e := 新列表
• := a新列表
• degree := 大小为 (n + 1) 的新列表并用 0 填充
• visit := 大小为 (n + 1) 的新列表并用 0 填充
• odd_vert := 大小为 (n + 1) 的新列表并填充
• 用 0
• 对于范围为 0 到 m 的 i，执行
  • 在 g[s[i]] 末尾插入 d[i]
  • 在 g[d[i]] 末尾插入 s[i]
  • degree[s[i]] := degree[s[i]] + 1
  • degree[d[i]] := degree[d[i]] + 1
• ans := 0, comp := 0
• 对于范围在 1 到 n + 1 内的 i，执行
  • 如果 visit[i] 与 0 相同，则
    • comp := comp + 1
    • dfs(g, visit, odd_vert, degree, comp, i)
    • 如果 odd_vert[comp] 与 0 相同，则
      • 在 e 的末尾插入 comp
    • 否则，
      • 在 o 的末尾插入 comp
  • 如果 o 的大小与 0 相同且 e 的大小与 1 相同，则
    • 返回0
  • 如果 o 的大小与 0 相同，则
    • 返回 e 的大小
  • 如果 e 的大小不与 0 相同，则
    • ans := ans + e 的大小
  • 对于 0 到 o 的大小范围内的 i，执行
    • ans := 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]
  

  输出

  1
  

  ---

  相关文章

  • Python 中通过 K 扩展列表
  • Python - 使用交替的 0 和 1 初始化列表
  • Python 中元组列表到字典的转换
  • Python - 从两个列表中配对，使得成对的元素不相同
  • 使用 Python 和 SQLite 的 SQL
  • 使用 pytrie 模块在 Python 中进行前缀匹配
  • 创建和访问 Python 包
  • 如何使用正则表达式和数据类型选择多个 DataFrame 列
  • 如何在 Pandas 中查找和过滤重复行?
  • 用 Python 编写程序以正确的顺序查找机场?

  ---

  有用资源

  • python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

  ---

  打印 下一节:在 Python 中从三个不同的数组中找出三个元素，使得 a + b + c = sum ❯❮ 上一节:在 Python 中，以二进制字符串的形式给出比分，找出比赛的获胜者