EWTD

5

Sep 20th, 2021
1,214
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. package main
  4.  
  5.  
  6.  
  7.  
  8. import (
  9.     "C"
  10.     "fmt"
  11.     "math"
  12. )
  13.  
  14. func filling_dist(dist []int, n int)  {for i:=0; i < n; i++{dist[i] = math.MaxInt32}}
  15.  
  16. func filling_edge(g []Vertex, m int)  {
  17.     var a,b int
  18.     for i:=0; i < m; i++{
  19.         fmt.Scan(&a, &b)
  20.         g[a].edges = append(g[a].edges, b)
  21.         g[b].edges = append(g[b].edges, a)
  22.     }
  23. }
  24.  
  25. func flags(flag bool){if !flag{fmt.Printf("-\n")}}
  26.  
  27. func check(k int, g []Vertex, dist []int)  {
  28.     var c int
  29.     for i:=0;i<k;i++{
  30.         fmt.Scan(&c)
  31.         g[c].base = true
  32.         dist[c] = 0
  33.     }
  34. }
  35.  
  36. type Vertex struct {
  37.     base bool
  38.     used bool
  39.     edges []int
  40. }
  41. func main(){
  42.     var n, m, k int
  43.     fmt.Scan(&n, &m)
  44.     queue := make([]int,0)
  45.     dist := make([]int,n)
  46.     candidates := make([]int, n)
  47.     graph := make([]Vertex,n)
  48.     BfsInner := func(g[]Vertex,  n int, queue []int, dist,candidates []int) {
  49.         for i:= 0; i < n; i++{
  50.             if g[i].base && !g[i].used{
  51.                 for j := 0; j < n; j++{if g[j].used && !g[j].base{g[j].used = false}}
  52.                 g[i].used = true
  53.                 queue = append(queue,i)
  54.                 for len(queue) > 0{
  55.                     current_vertex := queue[0]
  56.                     queue = queue[1:]
  57.                     for j:= 0; j < len(g[current_vertex].edges); j++{
  58.                         to := g[current_vertex].edges[j]
  59.                         if !g[to].used && !g[to].base{
  60.                             if dist[to] != 0 && dist[to] == dist[current_vertex]+1{candidates[to]++}
  61.                             dist[to] = dist[current_vertex]+1
  62.                             g[to].used = true
  63.                             queue = append(queue,to)
  64.                         }
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     filling_dist(dist, n)
  71.     filling_edge(graph, m)
  72.     fmt.Scan(&k)
  73.     check(k, graph, dist)
  74.     BfsInner(graph, n, queue, dist,candidates)
  75.     flag := false
  76.     for i:=0; i<n; i++{
  77.         if candidates[i] == k-1{
  78.             fmt.Printf("%d ",i); flag = true
  79.         }
  80.     }
  81.     flags(flag)
  82.     return
  83. }
RAW Paste Data