Advertisement
Pug_coder

trash

May 6th, 2021
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 2.14 KB | None | 0 0
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "github.com/skorobogatov/input"
  6. )
  7.  
  8.  
  9.  
  10.  
  11. type Vertex struct {
  12.     neighbors []int
  13.     distance []int
  14. }
  15. type Queue struct {
  16. Storage []int
  17. }
  18.  
  19. func NewQueue() *Queue {
  20.     return &Queue{[]int{}}
  21. }
  22.  
  23. func min(a int, b int) bool{
  24.     if a > b {
  25.         return false
  26.     }
  27.     return true
  28. }
  29.  
  30. func (queue *Queue) Pop() int {
  31.     value := queue.Storage[0]
  32.     queue.Storage = queue.Storage[1:]
  33.     return value
  34. }
  35.  
  36. func (queue *Queue) Push(value int) {
  37.     queue.Storage = append(queue.Storage, value)
  38. }
  39.  
  40. func (queue Queue) IsEmpty() bool {
  41.     return len(queue.Storage) == 0
  42. }
  43.  
  44. func BFS(graph []Vertex, rootIndex, rootRelativeIndex int) {
  45.     queue := NewQueue()
  46.     queue.Push(rootIndex)
  47.     visited := make([]bool, len(graph))
  48.  
  49.     for !queue.IsEmpty() {
  50.         index := queue.Pop()
  51.         visited[index] = true
  52.         for _, uIndex := range graph[index].neighbors {
  53.             if visited[uIndex] == true {
  54.                 continue
  55.             }
  56.             visited[uIndex] = true
  57.             graph[uIndex].distance[rootRelativeIndex] = graph[index].distance[rootRelativeIndex] + 1
  58.             queue.Push(uIndex)
  59.         }
  60.     }
  61. }
  62.  
  63. func main() {
  64.     var n, m int
  65.     var graph []Vertex
  66.     input.Scanf("%d \n %d", &n, &m)
  67.     for i := 0; min(i,n); i++ {
  68.         var ver Vertex
  69.         ver.neighbors = make([]int, 0)
  70.         ver.distance = make([]int, 0)
  71.         graph = append(graph, ver)
  72.     }
  73.     for i := 0; i < m; i++ {
  74.         var indexA, indexB int
  75.         input.Scanf("%d %d", &indexA, &indexB)
  76.         graph[indexA].neighbors = append(graph[indexA].neighbors, indexB)
  77.         graph[indexB].neighbors = append(graph[indexB].neighbors, indexA)
  78.     }
  79.     var k int
  80.     input.Scanf("%d", &k)
  81.  
  82.     for i := 0; i < k; i++ {
  83.         var v int
  84.         input.Scanf("%d", &v)
  85.         for j := 0; j < n; j++ {
  86.             graph[j].distance = append(graph[j].distance, n)
  87.         }
  88.         BFS(graph, v, i)
  89.     }
  90.     //for i := 0; i < m; i++ {fmt.Println(graph[i])}
  91.     count := 0
  92.     for i := 0; i < n; i++ {
  93.         equal := true
  94.         for j := 1; j < k; j++ {
  95.             if graph[i].distance[j] != graph[i].distance[j - 1] || graph[i].distance[j] == n {
  96.                 equal = false
  97.                 break
  98.             }
  99.         }
  100.         if equal {
  101.             fmt.Printf("%d ", i)
  102.             count ++
  103.         }
  104.     }
  105.     if count == 0 {
  106.         fmt.Println("-")
  107.     }
  108.     //fmt.Printf("%d : len = %d\n", i, graph[i].distance[0])
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement