Advertisement
Ladies_Man

Equidistant v (Равноудал.вершины)

Jun 9th, 2014
272
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 2.78 KB | None | 0 0
  1. package main
  2. import "github.com/skorobogatov/input"
  3. import "fmt"
  4. import "math"
  5. import "os"
  6. type queue struct {
  7.         head  *el
  8.         tail  *el
  9.     count int
  10. }
  11. type vertex struct {
  12.     edge []int
  13.     mark bool
  14.     p    *edge
  15.     next *edge
  16. }
  17. type edge struct {
  18.     u, v, indx int
  19.     vertex     *vertex
  20.     next       *edge
  21. }
  22. type el struct {
  23.     u, v  *vertex
  24.     value int
  25.     next  *el
  26. }
  27. var n, m, k int
  28. var G []vertex
  29. var A []int
  30. var T []int
  31. var temp []float64
  32.  
  33. func abs(x int) int { if x < 0 { return -x }; return x }
  34.  
  35. func Enqueue(q *queue, value int) {
  36.     defer func() { q.count++ }()
  37.     if q.head == nil { q.head = &el{&G[0], &G[len(G)-1], value, nil};  q.tail = q.head
  38.     } else {
  39.         t := q.tail
  40.             q.tail = &el{&G[0], &G[len(G)-1], value, nil}
  41.         t.next = q.tail
  42.     }
  43. }
  44.  
  45. func Dequeue(q *queue) int {
  46.     ret_val := q.head.value
  47.     q.head = q.head.next
  48.     q.count--
  49.     return ret_val
  50. }
  51.  
  52. func Mark(ptr int) {
  53.     if 2 == ptr {
  54.         for i := 0; i < n; i++ { G[i].mark = false }
  55.     } else {
  56.         for i := 0; i < n; i++ { G[i].edge, A[i] = make([]int, n), 777 }
  57.     }
  58.     if 0 > ptr { for i := 0; i < len(temp); i++ { temp[i] = math.Inf(1) } }
  59. }
  60.  
  61. func BFS(v int) (queue, bool) {
  62.         var f bool = false
  63.     Mark(2)
  64.     var q queue
  65.     dist := make([]int, n+m)
  66.     Enqueue(&q, v)
  67.     G[v].mark = true
  68.     for q.count != 0 {
  69.         u := Dequeue(&q)
  70.         v := G[u]
  71.         for i := range v.edge {
  72.             if 0 != v.edge[i] && !G[i].mark {
  73.                 G[i].mark = true
  74.                 Enqueue(&q, i)
  75.                 if i != u { dist[i] += dist[u] + 1 }
  76.             }
  77.         }
  78.     }
  79.     for i := 0; i < n; i++ { if A[i] == dist[i] && dist[i] != 0 || A[i] == 777 { Enqueue(&q, i); A[i] = dist[i] } else { A[i] = (int)(math.Inf(1)) }; f = true }
  80.     return q, f
  81. }
  82.  
  83. func nless2(num int) bool {
  84.     if 1 == num { return false
  85.     } else if 2 == num { fmt.Printf("-"); return false }
  86.     return true
  87. }
  88.  
  89. func get_ans(q *queue) {
  90.     var i int
  91.     var mark bool = false
  92.     Mark(-(abs(q.count)))
  93.     for 0 != q.count {
  94.         temp[i] = (float64)(Dequeue(q))
  95.         mark = true
  96.         i++
  97.     }
  98.     if !mark { fmt.Printf("-"); os.Exit(0) }
  99.     for i := range temp { if temp[i] != math.Inf(1) && temp[i] != temp[i+1] { fmt.Printf("%1.f ", temp[i]) } }
  100. }
  101.  
  102. func main() {
  103.     var m, u, v, k int
  104.     var q queue
  105.         var f bool = false
  106.     input.Scanf("%d\n%d\n", &n, &m)
  107.     if p := nless2(n); !(p) { os.Exit(0) }
  108.     G = make([]vertex, n)
  109.     A = make([]int, n)
  110.     T = make([]int, 0)
  111.         E := make([]edge, m)
  112.     temp = make([]float64, n)
  113.     Mark(1)
  114.     for i := 0; i < m; i++ {
  115.             input.Scanf("%d %d\n", &u, &v)
  116.         G[u].edge[v], G[v].edge[u] = 1, 1
  117.         E[i].v, E[i].u = v, u
  118.         E[i].vertex = &G[u]
  119.                 if i > 0 { E[i-1].next = E[i].next }
  120.     }
  121.     input.Scanf("%d\n", &k)
  122.     for i := 0; i < k; i++ { input.Scanf("%d", &v); T = append(T, v) }
  123.     for i := 0; i < k; i++ { q,f = BFS(T[i]) }
  124.         if f { get_ans(&q) } else { os.Exit(0) }
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement