Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import (
- "fmt"
- "github.com/skorobogatov/input"
- )
- type Vertex struct {
- neighbors []int
- distance []int
- }
- type Queue struct {
- Storage []int
- }
- func NewQueue() *Queue {
- return &Queue{[]int{}}
- }
- func min(a int, b int) bool{
- if a > b {
- return false
- }
- return true
- }
- func (queue *Queue) Pop() int {
- value := queue.Storage[0]
- queue.Storage = queue.Storage[1:]
- return value
- }
- func (queue *Queue) Push(value int) {
- queue.Storage = append(queue.Storage, value)
- }
- func (queue Queue) IsEmpty() bool {
- return len(queue.Storage) == 0
- }
- func BFS(graph []Vertex, rootIndex, rootRelativeIndex int) {
- queue := NewQueue()
- queue.Push(rootIndex)
- visited := make([]bool, len(graph))
- for !queue.IsEmpty() {
- index := queue.Pop()
- visited[index] = true
- for _, uIndex := range graph[index].neighbors {
- if visited[uIndex] == true {
- continue
- }
- visited[uIndex] = true
- graph[uIndex].distance[rootRelativeIndex] = graph[index].distance[rootRelativeIndex] + 1
- queue.Push(uIndex)
- }
- }
- }
- func main() {
- var n, m int
- var graph []Vertex
- input.Scanf("%d \n %d", &n, &m)
- for i := 0; min(i,n); i++ {
- var ver Vertex
- ver.neighbors = make([]int, 0)
- ver.distance = make([]int, 0)
- graph = append(graph, ver)
- }
- for i := 0; i < m; i++ {
- var indexA, indexB int
- input.Scanf("%d %d", &indexA, &indexB)
- graph[indexA].neighbors = append(graph[indexA].neighbors, indexB)
- graph[indexB].neighbors = append(graph[indexB].neighbors, indexA)
- }
- var k int
- input.Scanf("%d", &k)
- for i := 0; i < k; i++ {
- var v int
- input.Scanf("%d", &v)
- for j := 0; j < n; j++ {
- graph[j].distance = append(graph[j].distance, n)
- }
- BFS(graph, v, i)
- }
- //for i := 0; i < m; i++ {fmt.Println(graph[i])}
- count := 0
- for i := 0; i < n; i++ {
- equal := true
- for j := 1; j < k; j++ {
- if graph[i].distance[j] != graph[i].distance[j - 1] || graph[i].distance[j] == n {
- equal = false
- break
- }
- }
- if equal {
- fmt.Printf("%d ", i)
- count ++
- }
- }
- if count == 0 {
- fmt.Println("-")
- }
- //fmt.Printf("%d : len = %d\n", i, graph[i].distance[0])
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement