fork download
copy 
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. const INF = int(1e9)
  6.  
  7. func main() {
  8. 	var n, m int
  9. 	fmt.Scan(&n, &m)
  10.  
  11. 	g := make([][]int, n)
  12. 	for i := 0; i < m; i++ {
  13. 		var a, b int
  14. 		fmt.Scan(&a, &b)
  15. 		a--
  16. 		b--
  17. 		g[a] = append(g[a], b)
  18. 		g[b] = append(g[b], a)
  19. 	}
  20.  
  21. 	best := INF
  22.  
  23. 	dist := make([]int, n)
  24. 	parent := make([]int, n)
  25. 	q := make([]int, n)
  26.  
  27. 	for s := 0; s < n; s++ {
  28. 		for i := 0; i < n; i++ {
  29. 			dist[i] = -1
  30. 			parent[i] = -1
  31. 		}
  32.  
  33. 		head, tail := 0, 0
  34. 		dist[s] = 0
  35. 		q[tail] = s
  36. 		tail++
  37.  
  38. 		for head < tail {
  39. 			v := q[head]
  40. 			head++
  41.  
  42. 			if dist[v]*2+1 >= best {
  43. 				continue
  44. 			}
  45.  
  46. 			for _, to := range g[v] {
  47. 				if dist[to] == -1 {
  48. 					dist[to] = dist[v] + 1
  49. 					parent[to] = v
  50. 					q[tail] = to
  51. 					tail++
  52. 				} else if parent[v] != to { 
  53. 					cycleLen := dist[v] + dist[to] + 1
  54. 					if cycleLen < best {
  55. 						best = cycleLen
  56. 					}
  57. 				}
  58. 			}
  59. 		}
  60. 	}
  61.  
  62. 	if best == INF {
  63. 		fmt.Print(-1)
  64. 	} else {
  65. 		fmt.Print(best)
  66. 	}
  67. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
3 3
1 2
2 3
1 3
stdout
copy 
3
https://ideone.com/p3nh4Y
language:
Go (go 1.12.1)
created:
1 day ago
visibility:
public

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!