Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "C"
- "fmt"
- "math"
- )
- func filling_dist(dist []int, n int) {for i:=0; i < n; i++{dist[i] = math.MaxInt32}}
- func filling_edge(g []Vertex, m int) {
- var a,b int
- for i:=0; i < m; i++{
- fmt.Scan(&a, &b)
- g[a].edges = append(g[a].edges, b)
- g[b].edges = append(g[b].edges, a)
- }
- }
- func flags(flag bool){if !flag{fmt.Printf("-\n")}}
- func check(k int, g []Vertex, dist []int) {
- var c int
- for i:=0;i<k;i++{
- fmt.Scan(&c)
- g[c].base = true
- dist[c] = 0
- }
- }
- type Vertex struct {
- base bool
- used bool
- edges []int
- }
- func main(){
- var n, m, k int
- fmt.Scan(&n, &m)
- queue := make([]int,0)
- dist := make([]int,n)
- candidates := make([]int, n)
- graph := make([]Vertex,n)
- BfsInner := func(g[]Vertex, n int, queue []int, dist,candidates []int) {
- for i:= 0; i < n; i++{
- if g[i].base && !g[i].used{
- for j := 0; j < n; j++{if g[j].used && !g[j].base{g[j].used = false}}
- g[i].used = true
- queue = append(queue,i)
- for len(queue) > 0{
- current_vertex := queue[0]
- queue = queue[1:]
- for j:= 0; j < len(g[current_vertex].edges); j++{
- to := g[current_vertex].edges[j]
- if !g[to].used && !g[to].base{
- if dist[to] != 0 && dist[to] == dist[current_vertex]+1{candidates[to]++}
- dist[to] = dist[current_vertex]+1
- g[to].used = true
- queue = append(queue,to)
- }
- }
- }
- }
- }
- }
- filling_dist(dist, n)
- filling_edge(graph, m)
- fmt.Scan(&k)
- check(k, graph, dist)
- BfsInner(graph, n, queue, dist,candidates)
- flag := false
- for i:=0; i<n; i++{
- if candidates[i] == k-1{
- fmt.Printf("%d ",i); flag = true
- }
- }
- flags(flag)
- return
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement