Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package main
- import "fmt"
- type Triplet struct {
- first int
- second int
- third string
- }
- type Pair struct {
- one []int
- two string
- }
- func PrintMe(mas []Triplet, n int, m int, final []int) {
- for i:=0; i<m; i++ {
- fmt.Print(mas[i].first, " ")
- fmt.Print(mas[i].second, " ")
- fmt.Println(mas[i].third)
- }
- for i:=0; i<n; i++ {
- fmt.Print(final[i], " ")
- }
- fmt.Println()
- }
- func NewSet(n int) ([]int) {
- c := make([]int, n)
- for i:=0; i<n; i++ {
- c[i] = -1
- }
- return c
- }
- func Closure(mas []Triplet, z []int) ([]int) {
- C := NewSet(len(mas))
- //fmt.Println("z = ", z)
- for q:=0; q<len(z); q++ {
- if z[q] != -1 {
- DFS(mas, z[q], C)
- }
- }
- return C
- }
- func DFS(mas []Triplet, q int, C []int) {
- //fmt.Println("q = ", q)
- //fmt.Println("CB = ", C)
- if !Search(C, q) { //если q не принадлежит С
- for i:=0; i<len(C); i++ {
- if C[i] == -1 { //если первый элемент С пустой,
- C[i] = q //кидаю туда q
- break
- }
- }
- //fmt.Println("CD = ", C)
- for i:=0; i<len(mas); i++ {
- if mas[i].first == q && mas[i].third == "lambda" {
- DFS(mas, mas[i].second, C)
- }
- }
- }
- }
- func Search(Qn []int, qn int) (bool) {
- var eq bool
- for i:= range Qn {
- if Qn[i] == qn {
- eq = true
- break
- }
- }
- return eq
- }
- func newStack(n int) ([][]int) {
- stack := make([][]int, n, n)
- for i:=0; i<n; i++ {
- stack[i] = make([]int, n)
- }
- for i:=0; i<n; i++ {
- for j:=0; j<n; j++ {
- stack[i][j] = -1
- }
- }
- return stack
- }
- func Pop(stack [][]int) ([]int) {
- for i:=len(stack)-1; i>=0; i-- {
- //fmt.Println("!", i)
- if stack[i][0] != -1 {
- res := stack[i]
- return res
- }
- }
- return nil
- }
- func contains(Q [][]int, zz []int) bool {
- eq := true //принадледжит
- c:=0
- for i:=0; i<len(Q); i++ {
- for j:=0; j<len(Q); j++ {
- //fmt.Println("zz = ", zz[j], " q = ", Q[i][j], " i = ", i)
- if zz[j] == Q[i][j] {
- c++
- eq = true
- } else {
- eq = false
- break
- }
- if c == len(Q) {
- return true
- }
- }
- c = 0
- }
- return eq
- }
- func Push(stack [][]int, what []int, size int) ([]int){
- //fmt.Println("inside size = ", size)
- for i:=0; i<len(what); i++ {
- stack[size][i] = what[i]
- }
- return stack[size]
- }
- func Det(mas []Triplet, Final []int, q int) {
- n := len(mas)
- l := 1
- e:=make([]int, n)
- for i:=0; i<n; i++ {
- e[i] = -1
- }
- e[0] = q
- qo := Closure(mas, e)
- F := make([][]int, n, n)
- for i:=0; i<n; i++ {
- F[i] = make([]int, n)
- }
- for i:=0; i<n; i++ {
- for j:=0; j<n; j++ {
- F[i][j] = -1
- }
- }
- delta := make([]Pair, n)
- for i:=0; i<n; i++ {
- delta[i].one = append(delta[i].one, -1)
- }
- Q := make([][]int, n, n)
- for i:=0; i<n; i++ {
- Q[i] = make([]int, n)
- }
- for i:=0; i<n; i++ {
- for j:=0; j<n; j++ {
- Q[i][j] = -1
- }
- }
- for i:=0; i<len(qo); i++ {
- Q[0][i] = qo[i]
- //fmt.Println(Q[i])
- }
- stack := newStack(n*n)
- for i:=0; i<len(qo); i++ {
- stack[0][i] = qo[i]
- //fmt.Println("st = ",stack[0][i])
- }
- delta[0].one = qo
- delta[0].two = "nune"
- stackSize := 1
- for stackSize > 0 {
- fmt.Println("size = ", stackSize)
- z:= Pop(stack)
- fmt.Println(stack)
- fmt.Println("z = ", z)
- for u:=0; u<len(z); u++ {
- if Final[u] == 1 {
- for i:=0; i<len(F); i++ {
- if F[i][0] != -1 {
- F[i] = z
- break
- }
- }
- break
- }
- }
- VertexesOnLetter := make([]int, n)
- for a:=0; a<n; a++ {
- for i := 0; i < len(VertexesOnLetter); i++ {
- VertexesOnLetter[i] = -1
- }
- //fmt.Println("a = ", a)
- letter := mas[a].third
- fmt.Println("letter = ", letter)
- for i := 0; i < len(z); i++ {
- //fmt.Println("f = ", mas[i].first, " t = ", mas[i].third, " z = ", z[i], " l = ", letter)
- for j := 0; j < n; j++ {
- if mas[j].first == z[i] && mas[j].third == letter && !Search(VertexesOnLetter, mas[j].second) {
- for w := 0; w < len(VertexesOnLetter); w++ {
- if VertexesOnLetter[w] == -1 {
- VertexesOnLetter[w] = mas[j].second
- //fmt.Println("! = ", mas[j].second)
- break
- }
- }
- }
- }
- }
- fmt.Println("vL = ", VertexesOnLetter)
- zz := Closure(mas, VertexesOnLetter)
- //fmt.Println("zz!!zz = ", zz)
- //fmt.Println("Q!!Q = ", Q)
- eq := contains(Q, zz)
- //fmt.Println("! ", eq)
- if !eq {
- //fmt.Println("in eq")
- for i := 0; i < len(Q); i++ {
- if Q[i][0] == -1 {
- Q[i] = zz
- break
- }
- }
- stackSize++
- Push(stack, zz, stackSize)
- if l < n && letter != "lambda"{
- delta[l].one = zz
- delta[l].two = letter
- l++
- }
- }
- }
- stackSize--
- }
- for i:=0; i<l; i++ {
- for j:=0; j<l; j++ {
- if delta[i].one[j] != -1 {
- fmt.Print(delta[i].one[j], " ")
- }
- }
- fmt.Print(delta[i].two, " ")
- fmt.Println()
- }
- }
- func main() {
- var n, m, q int
- fmt.Scan(&n)
- fmt.Scan(&m)
- mas := make([]Triplet, m)
- for i:=0; i<m; i++ {
- fmt.Scan(&mas[i].first)
- fmt.Scan(&mas[i].second)
- fmt.Scan(&mas[i].third)
- }
- final := make([]int, n)
- for i:=0; i<n; i++ {
- fmt.Scan(&final[i])
- }
- fmt.Scan(&q)
- //PrintMe(mas, n, m, final)
- //C:= Closure(mas, n, z)
- //fmt.Print("C = ",C)
- Det(mas, final, q)
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement