📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: firefox970
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家电面面经:有向图包含目标点的最小环

🔗
taybson 2020-1-29 11:29:12 | 只看该作者
全局:
  1. # Python3 implementation of the approach
  2. from sys import maxsize as INT_MAX
  3. from collections import deque
  4. from collections import defaultdict
  5.   
  6. N = 100200

  7. gr = [0] * N
  8. for i in range(N):
  9.     gr[i] = []
  10.   
  11. # Function to add edge
  12. def add_edge(x, y):
  13.     global gr
  14.     gr[x].append(y)
  15.     gr[y].append(x)

  16. # Number of vertices
  17. V = 7

  18. def shortest_cycle(n):
  19.     dist = [int(1e9) for _ in range(V)]
  20.     parent = [-1 for _ in range(V)]
  21.     dist[n] = 0
  22.     q = deque()
  23.     q.append(n)
  24.     shortest = float('inf')
  25.     mp = defaultdict(list)
  26.     while q:
  27.         cur = q.popleft()
  28.         for child in gr[cur]:
  29.             if dist[child] == int(1e9):
  30.                 dist[child] = dist[cur] + 1
  31.                 parent[child] = cur
  32.                 q.append(child)
  33.             elif parent[child] != cur and parent[cur] != child:
  34.                 if shortest > dist[cur] + dist[child] + 1:
  35.                     shortest = dist[cur] + dist[child] + 1
  36.                     path = [cur, child]
  37.                     p = cur
  38.                     d = child
  39.                     while parent[p] != n:
  40.                         p = parent[p]
  41.                         path.insert(0, p)
  42.                     while parent[d] != n:
  43.                         d = parent[d]
  44.                         path.append(d)
  45.                     path.append(n)
  46.                     mp[shortest].append(path)

  47.     print(mp[shortest]) #[2, 6, 1, 4, 3]
  48.     return shortest


  49. # Add edges
  50. add_edge(0, 6)
  51. add_edge(0, 5)
  52. add_edge(5, 1)
  53. add_edge(1, 6)
  54. add_edge(2, 6)
  55. add_edge(2, 3)
  56. add_edge(3, 4)
  57. add_edge(4, 1)

  58. # Function call
  59. print(shortest_cycle(3))
复制代码


本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
回复

使用道具 举报

🔗
lsssss 2020-2-2 04:19:30 | 只看该作者
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表