CriticalWay

package main

import (
    "fmt"
    "github.com/skorobogatov/input"
    "sort"
    "strconv"
)
type peak struct{
    name string;
    comp int;
    list []*peak;
    T1 int;
    low int;
    value int;
    color int;
    sum int;
    marker bool;
    list_sum []*peak;
    out []*peak;
}
type arrPeak [] * peak
func partiton( low int, high int, less func(i, j int )bool, swap func(i, j int)) int{
    i := low
    for j := low; j < high; j++ {
        if less(j,high) {
            swap(i,j)
            i++
        }
    }
    swap(i,high)
    return i
}
func quickSortRec(low int, high int, less func(i, j int) bool, swap func(i, j int)){
    if low < high{
        q := partiton(low, high, less ,swap)
        quickSortRec(low , q - 1, less, swap)
        quickSortRec( q + 1, high, less, swap)
    }
}
func QuickSort(n int, less func(i, j int) bool,swap func(i, j int)) {
    quickSortRec(0, n - 1, less, swap)
}

var time = 1
var count = 1
var index = 0
var stack arrPeak
func Tarjan(l arrPeak, stack arrPeak){
    for _, v := range l{
        if v.T1 == 0{
            VisitVertex_Tarjan(l, v, stack)
        }
    }
}

func VisitVertex_Tarjan(l arrPeak, v *peak, stack arrPeak){
    v.T1 = time
    v.low = time
    time++
    stack[index] = v
    index++
    for _, i := range v.list{
        u := i
        if u.T1 == 0{
            VisitVertex_Tarjan(l, u, stack)
        }
        if u.comp == 0 && v.low > u.low{
            v.low = u.low
        }
    }
    if v.T1 == v.low{
        index--
        u := stack[index]
        u.comp = count
        for u != v{
            index--
            u = stack[index]
            u.comp = count
        }
        count++
    }
}

func dfs(data_name arrPeak){
    queue := make(arrPeak, len(data_name))
    indexin := 0
    for _, w := range data_name{
        if !w.marker && w.color == -1{
            w.marker = true
            queue[indexin] = w
            indexin++
            for indexin > 0{
                indexin--
                v := queue[indexin]
                for _, u := range v.list{
                    if ! u.marker{
                        u.marker = true
                        queue[indexin] = u
                        indexin++
                        u.color = -1
                    }
                }
            }
        }
    }
}
func in(t *peak, out arrPeak) bool{
    for _, i := range out{
        if i == t{
            return true
        }
    }
    return false
}
func (arr arrPeak) Len() int {return len(arr)}
func (arr arrPeak) Less(i,j int) bool {
    a, b := arr[i].sum, arr[j].sum
    return a > b
}
func (arr arrPeak) Swap(i, j int) {
    arr[i], arr[j] = arr[j], arr[i]
}
func sortedSum(data arrPeak){
    if len(data) > 1{
        sort.Sort(data)
    }
}
func sortedName(data arrPeak){
    if len(data) > 1{
        QuickSort(len(data) ,
            func (i, j int) bool {
                return data[i].name < data[j].name},
            func (i, j int) { data[i], data[j] = data[j], data[i]},
        )
    }
}
func main() {
    symbol := ';'
    data_name := make(arrPeak, 0)
    for symbol == ';'{
        str := input.Gets()
        for str[len(str)-1] == '<'{
            str += input.Gets()
        }
        name := &peak{}
        i := 0
        symbol = '.'
        for i < len(str){
            if str[i] == '('{
                j := i+1
                for j = i+1; str[j] != ')'; j++{
                }
                name.value, _ = strconv.Atoi(str[i+1: j])
                i = j
            }else if (str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'){
                j := i
                for j < len(str) && str[j] != ';' && str[j] != '(' && str[j] != ' '{
                    j++
                }
                n := str[i:j]
                flag := 0
                var k *peak
                for _, chek := range data_name{
                    if chek.name == n{
                        flag = 1
                        k = chek
                        break
                    }
                }
                if flag == 0{
                    k = &peak{
                        name: n,
                        comp: 0,
                        T1: 0,
                        color: 0,
                        sum: 0,
                        marker: false,
                    }
                    data_name = append(data_name, k)
                }
                if name != nil{
                    if name.name == k.name{
                        name.color = -1
                    }
                    flag = 1
                    for _, h := range name.list{
                        if h == k{
                            flag = 0
                        }
                    }
                    if flag == 1{
                        name.list = append(name.list, k)
                    }
                }
                name = k
                i = j
            }else if str[i] == ' ' || str[i] == '<'{
                i++
            }else if str[i] == ';'{
                symbol = ';'
                i++
            }else{
                i++
            }
        }
    }
    stack = make(arrPeak, len(data_name))
    Tarjan(data_name, stack)
    inf := make([]int, count)

    for _, i := range data_name{
        inf[i.comp - 1]++
    }
    for _, i := range data_name{
        if inf[i.comp - 1] >= 2{
            i.color = -1
            for _, j := range i.list{
                j.color = -1
            }
        }
    }
    dfs(data_name)
    queue := make(arrPeak, len(data_name))
    indexin := 0
    for _, w := range data_name{
        if !w.marker && w.color != -1{
            w.marker = true
            queue[indexin] = w
            indexin++
            w.list_sum = append(w.list_sum, w)
            w.sum = w.value
            for indexin > 0{
                indexin--
                v := queue[indexin]
                for _, u := range v.list{
                    if u.color != -1 && (! u.marker || v.sum + u.value > u.sum){
                        u.marker = true
                        queue[indexin] = u
                        indexin++
                        u.sum = v.sum + u.value
                        u.list_sum = make(arrPeak, 0)
                        for _, k := range v.list_sum{
                            u.list_sum = append(u.list_sum, k)
                        }
                        u.list_sum = append(u.list_sum, u)
                        u.out = make(arrPeak, 0)
                        u.out = append(u.out, v)
                    }else if u.color != -1 && v.sum + u.value == u.sum{
                        u.marker = true
                        queue[indexin] = u
                        indexin++
                        u.out = append(u.out, v)
                        for _, k := range v.list_sum{
                            u.list_sum = append(u.list_sum, k)
                        }
                    }
                }
            }
        }
    }
    sortedSum(data_name)
    max := data_name[0].sum
    for _, i := range data_name{
        if i.sum == max{
            for _, k := range i.list_sum{
                k.color = 1
            }
        }else{
            break
        }
    }
    sortedName(data_name)
    fmt.Println("digraph {")
    for _, i := range data_name{
        if i.color == 1{
            a := i.name
            fmt.Printf(`  %s [label = "%s(%d)", color = red]`, a, a, i.value)
            fmt.Printf("\n")
        }else if i.color == -1{
            a := i.name
            fmt.Printf(`  %s [label = "%s(%d)", color = blue]`, a, a, i.value)
            fmt.Printf("\n")
        }else{
            a := i.name
            fmt.Printf(`  %s [label = "%s(%d)"]`, a, a, i.value)
            fmt.Printf("\n")
        }
    }
    for _, t := range data_name{
        if len(t.list) > 1{
            QuickSort(  len(t.list) ,
                func (i, j int) bool {
                    return t.list[i].name < t.list[j].name},
                func (i, j int) { t.list[i], t.list[j] = t.list[j], t.list[i]},
            )
        }
        for _, i := range t.list{
            if t.color == 1 && i.color == 1 && in(t, i.out){
                fmt.Printf("  %s -> %s [color = red]\n", t.name, i.name)
            }else if t.color == -1 && i.color == -1{
                fmt.Printf("  %s -> %s [color = blue]\n", t.name, i.name)
            }else {
                fmt.Printf("  %s -> %s\n", t.name, i.name)
            }
        }
    }
    fmt.Println("}")
}