tretyaya

package main

import (
    "fmt"
)

type Vertex struct {
    i int
    parent *Vertex
    depth int
}

/*func DFS(used []int, mass [][]int, ind int, begin int, m int, n int, k *int, help []bool) {
    for i:=0; i<n; i++ {
        used[i] = -1
    }
    /*var eq = false
    for i:=0; i<m; i++ {
        if mass[begin][i] != 0 {
            eq = true
            break
        }
    }
    if !eq {
        begin = 0
    }
    if !help[begin] {
        begin = 0
    }
    VisitVertex(used, mass, ind, begin, m, n, k)
    //}
    //}
}

func VisitVertex(used []int, mass [][]int, ind int, begin int, m int, n int, k *int) {
    used[begin] = *k
    //fmt.Println(" i = ", ind)
    (*k)++
    for i:=0; i<m; i++ {
        if used[mass[begin][i]] == -1 {
            //ind++
            VisitVertex(used, mass, ind, mass[begin][i], m, n, k)
        }
    }

} */
func DFS(mass [][]int, begin int, m int, n int, Num [][]int, NumNew [][]int, Str [][]string, StrNew[][]string) ([][]int, [][]string, int){
    used := make([]bool, n)
    stack := newStack(n)
    sizeStack := 0
    arr := make([] int, n)
    count := 0
    stack[sizeStack] = begin
    sizeStack++
    for sizeStack > 0 {
        sizeStack--
        v := stack[sizeStack]
        if !used[v] {
            used[v] = true
            fmt.Println("arr[",v,"] = ",used[v])
            arr[v] = count
            fmt.Println("cc arr[",v,"] = ",arr[v])
            count++
        }
        for i := m - 1; i > -1; i-- {
            u := mass[v][i]
            if !used[u] {
                stack[sizeStack] = u
                sizeStack++
            }
        }
    }
    for i := 0; i < n; i++ {
        fmt.Println("used[",i,"] = ",arr[i])
    }
    fmt.Println("co = ", count)
    NumNew, StrNew = Change(arr, used,  Num, NumNew, count, m, Str, StrNew, n)
    return NumNew, StrNew, count
}

func newStack(n int) []int  {
    stack := make([]int, n*n)
    return stack
}

func Search(used []int, f int) (int) {
    for i := range used {
        if used[i] == f {
            return i
        }
    }
    return 0
}

func Search1(Qn []int, qn int) (bool) {
    var eq bool
    if Qn[qn] != -1 {
        eq = true
    }
    /*for i:= range Qn {
        if Qn[i] == qn {
            eq = true
        }
    }*/
    return eq
}

func Change(used []int, b []bool, mass [][]int, NumNew [][]int, k int, m int, Str [][]string, StrNew [][]string, n int) ([][]int, [][]string) {
    fmt.Println("!k = ",k)

    /*for i := 0; i < k; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(mass[i][j], " ")
        }
        fmt.Println()
    }

    for i := 0; i < n; i++ {
        if b[i] {
            for j := 0; j < m; j++ {
                if b[i] {
                    NumNew[used[i]][j] = used[mass[i][j]]
                }
            }
        }
    }
    fmt.Println("aaaaaaaaaa")
    for i := 0; i < k; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(NumNew[i][j], " ")
        }
        fmt.Println()
    }
    fmt.Println("aaaaaaaaaa")
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
                if Str[Search(used, i)][j] != "" {
                    StrNew[i][j] = Str[Search(used, i)][j]
                    fmt.Print(Str[Search(used, i)][j], " ")
                    //fmt.Print(StrNew[i][j], " ")
                }
            }
        fmt.Println()
    }*/
    for i := 0; i < n; i++ {
        if b[i] {
            StrNew[used[i]] = Str[i]
            for j := 0; j < m; j++ {
                NumNew[used[i]][j] = used[mass[i][j]]
            }
        }
    }
    fmt.Println("aaaaaaaaaa")
    for i := 0; i < k; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(NumNew[i][j], " ")
        }
        fmt.Println()
    }
    fmt.Println("aaaaaaaaaa")
    return NumNew, StrNew
}

func Find(x *Vertex) (*Vertex) {
    var root *Vertex
    if (x.parent == x) {
        root = x
        return root
    } else {
        x.parent = Find(x.parent)
        root = x.parent
        return root
    }
}

func Union(x *Vertex, y *Vertex) {
    var rootX = Find(x)
    var rootY = Find(y)
    if rootX.depth < rootY.depth {
        rootX.parent = rootY
    } else {
        rootY.parent = rootX
        if rootX.depth == rootY.depth && rootX != rootY {
            rootX.depth = rootX.depth + 1
        }
    }
}

func Split(n int, m int, delta [][]int, fi [][]string, pi []int) (int, []int){
    var mn= n
    var eq bool
    Q := make([]Vertex, n)
                                    //по сути как со сплитом1, ток к+1 эквивалентность, вроде как на шаг вглубь
    for q:=0; q < n; q++ {
        Q[q].i = q
        Q[q].parent = &Q[q]
        Q[q].depth = 0
    }
    for q1:=0; q1<n; q1++ {
        for q2:=0; q2<n; q2++ {
            if pi[Q[q1].i] == pi[Q[q2].i] && Find(&Q[q1]) != Find(&Q[q2]) {
                eq = true
                for x:=0; x<m; x++ {
                    var w1 = delta[Q[q1].i][x]
                    var w2 = delta[Q[q2].i][x]
                    if pi[w1] != pi[w2] {
                        eq = false
                        break
                    }
                }
                if eq {
                    Union(&Q[q1], &Q[q2])
                    mn--
                }
            }
        }
    }
    for q:=0; q<n; q++ {
        pi[Q[q].i] = Find(&Q[q]).i
        fmt.Println("p!i = ",pi[Q[q].i], " ")
    }
    return mn, pi
}

func Split1(n int, m int, NumNew [][]int, StrNew [][]string) (int, []int) {
    var eq bool
    var mn = n           //общее кол-во классов
    pi := make([]int, n) //каждому состоянию ставится в соответствие корень класса, кот оно принадлежит
    Q := make([]Vertex, n)

    for q:=0; q < n; q++ {
        Q[q].i = q
        Q[q].parent = &Q[q]
        Q[q].depth = 0
    }

    for q1:=0; q1<n; q1++ {
        for q2:=0; q2<n; q2++ {
            if Find(&Q[q1]) != Find(&Q[q2]) { //если переходы по любому входгному сигналу дают одинаковый
                eq = true                       //сигнал, то надо их объединить
                for x:=0; x<m; x++ {
                    if StrNew[q1][x] != StrNew[q2][x] {
                        eq = false
                        break
                    }
                }
                if eq {
                    Union(&Q[q1], &Q[q2])
                    mn--
                }
            }
        }
    }
    for q:=0; q<n; q++ {
        pi[Q[q].i] = Find(&Q[q]).i
        fmt.Println("pi = ",pi[Q[q].i], " ")
    }
    fmt.Println("mn = ", mn)

    return mn, pi
}

func AufenkampHohn(n int, m int, NumNew [][]int, StrNew [][]string) ([][]int, [][]string, []int){
    m_res, pi := Split1(n, m, NumNew, StrNew)
    var m_res1 int
    for {
        m_res1, pi = Split(n, m, NumNew, StrNew, pi) //смотрим глубину эквивалентности
        if m_res == m_res1 { //не может быть больше, чем состояний автомата
            break
        }
        m_res = m_res1
    }
    fmt.Println("pi:")
    for i := 0; i < n; i++ {
        fmt.Print(pi[i], " ")
    }
    fmt.Println()

    Qn := make([]int, n)

    delta := make([][]int, n) //цифры
    fi := make([][]string, n) //буквы
    for i:=0; i<n; i++ {
        delta[i] = make([]int, m)
        fi[i] = make([]string, m)
    }
    c := 0
    //eq := make([]bool, n)
    for i :=0; i < n ;i++ {
        Qn[i] = -1
    }
    help := make([]bool, n)
    for q:=0; q<n; q++ {
        var qn = pi[q]
        if !Search1(Qn, qn) { //принадлежит ли qn массиву Qn
        //if !eq[qn]{
        // eq[qn] = true
        c++
            Qn[q] = q
            for x:=0; x<m; x++ {
                help[qn] = true
                delta[qn][x] = pi[NumNew[q][x]]
                fmt.Print(delta[qn][x], " ")
                fi[qn][x] = StrNew[q][x]
            }
            fmt.Println()
        }
    }
    fmt.Println("c = " , c)
    fmt.Println("here")
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(delta[i][j], " ")
        }
        fmt.Println()
    }

    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(fi[i][j], " ")
        }
        fmt.Println()
    }
    fmt.Println("here")
    return delta, fi, pi
}

func main() {
    var n, m, q, k int

    fmt.Scan(&n)
    fmt.Scan(&m)
    fmt.Scan(&q)
    //n = 3; m = 2; q = 1

    Num := make([][]int, n)
    Str := make([][]string, n)
    NumNew := make([][]int, n)
    StrNew := make([][]string, n)
    //used := make([]int, n)
    help := make([]int, n)
    for i:=0; i<n; i++ {
        Num[i] = make([]int, m)
        NumNew[i] = make([]int, m)
        Str[i] = make([]string, m)
        StrNew[i] = make([]string, m)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            fmt.Scan(&Num[i][j])
        }
    }
    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            fmt.Scan(&Str[i][j])
        }
    }

    /*Num[0][0] = 1; Num[0][1] = 0; Num[1][0] = 2; Num[1][1] = 0; Num[2][0] = 2; Num[2][1] = 2
    Str[0][0] = "x"; Str[0][1] = "y"; Str[1][0] = "y"; Str[1][1] = "x"; Str[2][0] = "x"; Str[2][1] = "y"*/

    /*for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            fmt.Print("Num[",i,"][",j,"] = ", Num[i][j]," ")
        }
        fmt.Println()
    }*/
    Num, Str, help = AufenkampHohn(n, m, Num, Str)

    fmt.Println("n = ", n, " m = ", m, " len = ", len(Num))

    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            fmt.Print("Num[",i,"][",j,"] = ", Num[i][j]," ") //до канонизации, но уже убрано ненужное
        }
        fmt.Println()
    }
//func DFS(mass [][]int, begin int, m int, n int, Num [][]int, NumNew [][]int, Str [][]string, StrNew[][]string) {
    NumNew, StrNew, k = DFS(Num, help[q], m, n, Num, NumNew, Str, StrNew)
    //q = 0
    //fmt.Print(k, "\n", m, "\n", q, "\n")

    /*for i := 0; i < n; i++ {
        fmt.Println("used[",i,"] = ",used[i])
    }*/

    //Change(used, Num, NumNew, k, m, Str, StrNew, n) //тут закончена какнонизация
    /*for i := 0; i < n; i++ {
        fmt.Println("used[",i,"] = ",used[i])
    }*/
    //fmt.Println("n = ", n, " m = ", m, " len = ", len(Num))
    n = k
    //все, связанное с выводом
    alphabet := make([]byte, 27)
    q = 0
    for i:=0; i<27; i++ {
        alphabet[i] = (byte) (i+97)
    }
    fmt.Println("digraph {")
    fmt.Println("    rankdir = LR")
    fmt.Println("    dummy [label = \"\" , shape = none]")
    for i:=0; i<n; i++ {
        fmt.Println("    ",i," [shape = circle]")
    }
    fmt.Println("    dummy -> ", q)
    for i:=0; i<n; i++ {
        for j:=0; j<m; j++ {
            //fmt.Println("    ",q," -> ",goMatrix_delta[i][j]," [label = \"",array[j],"(",exitMatrix_fi[i][j],")\"]")
            fmt.Printf("     %d -> %d [label = \"%c(%s)\"]",i,NumNew[i][j],alphabet[j], StrNew[i][j])
            fmt.Println()
        }
        q++
    }
    fmt.Println("}")
}