teeds.go

package main

import "fmt"
import "os"
// import "sort"

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/


type node struct {
    num int
    propagation_base int
    link []int
}



// type DataList map[int]node

// func (receiver DataList) Less(a, b int) bool {
//     if len(receiver[a].link) > len(receiver[b].link) {
//         return true
//     }
//     return false
// }

// func (receiver DataList) Len() int {
//     return len(receiver)
// }

// func (receiver DataList) Swap(a, b int) {
//     receiver[a], receiver[b] = receiver[b], receiver[a]
// }

func main() {
    // n: the number of adjacency relations
    var n int
    fmt.Scan(&n)
    
    fmt.Fprintln(os.Stderr, "n:", n)
    
    
    
    
    var graph map[int]node
    graph = make(map[int]node)


    for i := 0; i < n; i++ {
        // xi: the ID of a person which is adjacent to yi
        // yi: the ID of a person which is adjacent to xi
        var xi, yi int
        fmt.Scan(&xi, &yi)
        
        graph[xi] = node {
            num:xi,
            propagation_base:-1,
            link:append(graph[xi].link, yi),
        }
        graph[yi] = node {
            num:yi,
            propagation_base:-1,
            link:append(graph[yi].link, xi),
        }
        

        
    }

    result := len(graph)

    depth := 0
    max := 0    
    bEnd := false
    for i:=0; i<len(graph); i++ {
        
        
        if len(graph[i].link) == 1 {
            TraverseGraph(graph, i, i, depth, &max, result, &bEnd)
            fmt.Fprintln(os.Stderr, "max:", max)
            break
        }
    }
    
    result = int((float32(max) / float32(2)) + 0.5)

    
    fmt.Println(result) // The minimal amount of steps required to completely propagate the advertisement
}

func TraverseGraph(graph map[int]node, base int, idx int, depth int, max *int, curmin int, bEnd *bool) {
    
    if *bEnd {
        return
    }
    
    depth++
    
    
    if curmin < depth {
        *bEnd = true
        return
    }
    
    graph[idx] = node {
        link: graph[idx].link,
        propagation_base: base,
    } 

    for i:=range graph[idx].link {
        
        if curmin < depth {
            *bEnd = true
            return
        }
        n := graph[idx].link[i]
        
        if graph[n].propagation_base == base {
            continue
        }
        
        if *max < depth {
            *max = depth        
        }
        
        TraverseGraph(graph, base, n, depth, max, curmin, bEnd)
    }
}