活跃农民
- 积分
- 432
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2013-3-14
- 最后登录
- 1970-1-1
|
- # Python3 implementation of the approach
- from sys import maxsize as INT_MAX
- from collections import deque
- from collections import defaultdict
-
- N = 100200
- gr = [0] * N
- for i in range(N):
- gr[i] = []
-
- # Function to add edge
- def add_edge(x, y):
- global gr
- gr[x].append(y)
- gr[y].append(x)
- # Number of vertices
- V = 7
- def shortest_cycle(n):
- dist = [int(1e9) for _ in range(V)]
- parent = [-1 for _ in range(V)]
- dist[n] = 0
- q = deque()
- q.append(n)
- shortest = float('inf')
- mp = defaultdict(list)
- while q:
- cur = q.popleft()
- for child in gr[cur]:
- if dist[child] == int(1e9):
- dist[child] = dist[cur] + 1
- parent[child] = cur
- q.append(child)
- elif parent[child] != cur and parent[cur] != child:
- if shortest > dist[cur] + dist[child] + 1:
- shortest = dist[cur] + dist[child] + 1
- path = [cur, child]
- p = cur
- d = child
- while parent[p] != n:
- p = parent[p]
- path.insert(0, p)
- while parent[d] != n:
- d = parent[d]
- path.append(d)
- path.append(n)
- mp[shortest].append(path)
- print(mp[shortest]) #[2, 6, 1, 4, 3]
- return shortest
- # Add edges
- add_edge(0, 6)
- add_edge(0, 5)
- add_edge(5, 1)
- add_edge(1, 6)
- add_edge(2, 6)
- add_edge(2, 3)
- add_edge(3, 4)
- add_edge(4, 1)
- # Function call
- print(shortest_cycle(3))
复制代码
|
本帖子中包含更多资源
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
|