fork download
copy 
  1. import math
  2. from collections import defaultdict
  3.  
  4. def bfs(graph, root, target):
  5. 	visited = set()
  6. 	queue = [[root]]
  7. 	if root == target:
  8. 		return 0
  9. 	while queue:
  10. 		path = queue.pop(0)
  11. 		node = path[-1]
  12. 		if node not in visited: 
  13. 			neighbours = graph[node]
  14. 			for neighbour in neighbours: 
  15. 				new_path = list(path)
  16. 				new_path.append(neighbour)
  17. 				queue.append(new_path)
  18. 				if neighbour == target:
  19. 					return len(new_path) - 1
  20. 			visited.add(node)
  21. 	return -1
  22.  
  23. def largest_fact(num):
  24. 	for i in range(2,int(math.sqrt(num))+1):
  25. 		if num%i==0:
  26. 			return num//i
  27. 	return 1
  28.  
  29. def update(graph,num):
  30. 	tmp = num
  31. 	while(True):
  32. 		if tmp==1:
  33. 			break
  34. 		lg_fact = largest_fact(tmp)
  35. 		graph[tmp].add(lg_fact)
  36. 		graph[lg_fact].add(tmp)
  37. 		tmp = lg_fact
  38.  
  39.  
  40. n1,n2 = map(int,input().split())
  41. graph = defaultdict(set)
  42. update(graph,n1)
  43. update(graph,n2)
  44. print(bfs(graph,n1,n2))
Success #stdin #stdout 0.02s 9184KB
comments (?)
stdin
copy 
9 9
stdout
copy 
0
https://ideone.com/2SCP0N
Path On Graph Codevita 2020
language:
Python 3 (python  3.12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!