Минимизация авт. Мили

package main
import (
        "fmt"
    "github.com/skorobogatov/input"
)
type Stack struct {
    data [] int
    top int
    capacity int
}

func (st Stack) isEmpty ()bool {
    return (st.top == 0)
}
func (st *Stack) push (x int) {
    if st.top == st.capacity {
        st.capacity*=2
        dub := make([] int, st.capacity)
        copy(dub, st.data)
        st.data = dub
    }
    st.data[st.top] = x
    st.top++
}
func (st *Stack) pop () int {
    st.top--
    return st.data[st.top]
}
func dfs (graph []Cond, n int, first int, m int) ([]Cond, int)  {
    var st Stack
    st.data = make([] int, n)
    st.top = 0
    st.capacity = n
    number := 0
    (&st).push(first)
    for !st.isEmpty() {
        v := st.pop()
        if graph[v].mark == -1 {
            graph[v].mark = 0
            graph[v].num = number
            number++
            (&st).push(v)
            for i:=m-1; i>=0; i-- {
                u := graph[v].edges[i].dest
                if graph[u].mark == -1 {
                    (&st).push(u)
                }
            }
        } else {
            if graph[v].mark == 0 {
                graph[v].mark = 1
            }
        }
    }
    return graph, number
}

type Edge struct {
    dest int
    label string
}

type Cond struct {
    i int
    parent *Cond
    depth int
    edges []Edge
    num int
    mark int
}

func ( t *Cond) makeSet () {
    t.parent = t
    t.depth = 0
}
func (t *Cond) find () *Cond {
    if t.parent == t {
        return t
    } else {
        t.parent  = t.parent.find()
        return t.parent
    }
}
func union (x, y *Cond) {
    rx := x.find()
    ry := y.find()
    if rx.depth < ry.depth {
        rx.parent = ry
    } else {
        ry.parent = rx
        if (rx.depth == ry.depth)&&(rx != ry) {
            rx.depth ++
        }
    }
}

func split1 (graph []Cond, n, m int, delta [][]int, fi [][]string) (int, []*Cond) {
    for i:=0; i<n; i++ {
        (&graph[i]).makeSet()
        graph[i].i = i
    }
    count := n
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
                if (&graph[i]).find() != (&graph[j]).find() {
                    eq := true
                    for k:=0; k<m; k++ {
                        if fi[i][k] != fi[j][k] {
                            eq = false
                            break
                        }
                    }
                    if eq {
                        union (&graph[i], &graph[j])
                        count --
                    }
                }
        }
    }
    pi := make ([] *Cond, n)
    for i:=0; i<n; i++ {
        pi[i] = (&graph[i]).find()
    }
    return count, pi
}

func split (graph []Cond, m, n int, delta [][]int, pi []*Cond) (int, []*Cond) {
    count := n
    for i:=0; i<n; i++ {
        graph[i].parent = &graph[i]
        graph[i].depth = 0
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            if (pi[i] == pi[j])&&((&graph[i]).find() != (&graph[j]).find()) {
                eq := true
                for k:=0; (k<m)&&eq; k++ {
                    if pi[ delta [i][k] ] != pi[ delta[j][k] ] {
                        eq = false
                    }
                }
                if eq {
                    union(&graph[i], &graph[j])
                    count--
                }
            }
        }
    }
    for i:=0; i<n; i++ {
        pi[i] = graph[i].find()
    }
    return count, pi
}

func belong (arr []Cond, q Cond, n int) bool {
    for i:=0; i<n; i++ {
        if (arr[i].i == q.i)&&(arr[i].parent == q.parent)&&(arr[i].depth == q.depth) {
            return true
        }
    }
    return false
}

func minimize (graph []Cond, delta [][]int, fi [][]string, n, m, first int) ([]Cond, [][]int, [][]string, int, int) {
    count, pi := split1(graph, n, m, delta, fi)
    var c int
    for ; ; {
        c, pi = split(graph, m, n, delta, pi)
        if count == c {
            break
        }
        count = c
    }
    var (
        min = make([]Cond, count)
        dmin = make ([][]int, count)
        fmin = make ([][]string, count)
        k int
    )
    for i:=0; i<count; i++ {
        dmin[i] = make([]int, m)
        fmin[i] = make([]string, m)
    }
    k = 0
    for i:=0; i<n; i++ {
        if (graph[i].i == pi[i].i)&&(graph[i].parent == pi[i].parent)&&(graph[i].depth == pi[i].depth) {
            graph[i].i = k
            k++
        } else {
            graph[i].i = pi[i].i
            }
    }
    k=0
    for i:=0; i<n; i++ {
        q1 := *pi[i]
        if !belong(min, q1, k) {
            min[k] = q1
            for j:=0; j<m; j++ {
                dmin[k][j] = pi[ delta[i][j] ].i
                fmin[k][j] = fi[i][j]
            }
            k++
        }
    }
    first = pi[first].i
    return min, dmin, fmin, count, first
}



func main() {
    var n, m, first, count int
    input.Scanf("%d\n%d\n%d\n", &n, &m, &first)
    var delta  = make([][]int, n)
    for i:=0; i<n; i++{
        delta[i] = make([]int, m)
    }
    var fi = make([][]string, n)
    for i:=0; i<n; i++{
        fi[i] = make([]string, m)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            input.Scanf("%d ", &delta[i][j])
        }
        input.Scanf("\n")
    }
    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            input.Scanf("%s ", &fi[i][j])
        }
        input.Scanf("\n")
    }
    var graph = make([]Cond, n)
    graph, delta, fi, n, first = minimize(graph, delta, fi, n, m, first)
    for i:=0; i<n; i++ {
        graph[i].edges = make([]Edge, m)
        graph[i].num = -1
        graph[i].mark = -1
        for j:=0; j<m; j++ {
            graph[i].edges[j] = Edge{ delta[i][j], fi[i][j] }
        }
    }
    graph, count = dfs (graph, n, first, m)
    delta = make([][]int, count)
    for i:=0; i<count; i++{
        delta[i] = make([]int, m)
    }
    fi = make([][]string, count)
    for i:=0; i<count; i++{
        fi[i] = make([]string, m)
    }
    for i:=0; i<n; i++ {
        num1 := graph[i].num
        if num1!=-1 {
            for j:=0; j<m; j++ {
                num2 := graph[ graph[i].edges[j].dest ].num
                delta[num1][j] = num2
                fi[num1][j] = graph[i].edges[j].label
            }
        }
    }
    n = count
    fmt.Printf("digraph {\n rankdir = LR\n dummy [label = \"\", shape = none]\n")
    for i:=0; i<n; i++ {
        fmt.Printf(" %d [shape = circle]\n", i)
    }
    fmt.Printf("dummy -> %d\n", 0)

    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            fmt.Printf ("%d -> %d [label = \"%c(%s)\"]\n", i, delta[i][j], byte ( int('a') + j), fi[i][j])
        }
    }
    fmt.Printf("}")
}