daily pastebin goal
91%
SHARE
TWEET

Untitled

a guest Jun 9th, 2018 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. type Triplet struct {
  6.     first int
  7.     second int
  8.     third string
  9. }
  10.  
  11. type Pair struct {
  12.     one []int
  13.     two string
  14. }
  15.  
  16. func PrintMe(mas []Triplet, n int, m int, final []int) {
  17.     for i:=0; i<m; i++ {
  18.         fmt.Print(mas[i].first, " ")
  19.         fmt.Print(mas[i].second, " ")
  20.         fmt.Println(mas[i].third)
  21.     }
  22.     for i:=0; i<n; i++ {
  23.         fmt.Print(final[i], " ")
  24.     }
  25.     fmt.Println()
  26. }
  27.  
  28. func NewSet(n int) ([]int) {
  29.     c := make([]int, n)
  30.     for i:=0; i<n; i++ {
  31.         c[i] = -1
  32.     }
  33.     return c
  34. }
  35.  
  36. func Closure(mas []Triplet, z []int) ([]int) {
  37.     C := NewSet(len(mas))
  38.     //fmt.Println("z = ", z)
  39.     for q:=0; q<len(z); q++ {
  40.         if z[q] != -1 {
  41.             DFS(mas, z[q], C)
  42.         }
  43.     }
  44.     return C
  45. }
  46.  
  47. func DFS(mas []Triplet, q int, C []int) {
  48.     //fmt.Println("q = ", q)
  49.     //fmt.Println("CB = ", C)
  50.     if !Search(C, q) {  //если q не принадлежит С
  51.         for i:=0; i<len(C); i++ {
  52.             if C[i] == -1 { //если первый элемент С пустой,
  53.                 C[i] = q    //кидаю туда q
  54.                 break
  55.             }
  56.         }
  57.         //fmt.Println("CD = ", C)
  58.         for i:=0; i<len(mas); i++ {
  59.             if mas[i].first == q && mas[i].third == "lambda" {
  60.                 DFS(mas, mas[i].second, C)
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. func Search(Qn []int, qn int) (bool) {
  67.     var eq bool
  68.     for i:= range Qn {
  69.         if Qn[i] == qn {
  70.             eq = true
  71.             break
  72.         }
  73.     }
  74.     return eq
  75. }
  76.  
  77. func newStack(n int) ([][]int)  {
  78.     stack := make([][]int, n, n)
  79.     for i:=0; i<n; i++ {
  80.         stack[i] = make([]int, n)
  81.     }
  82.     for i:=0; i<n; i++ {
  83.         for j:=0; j<n; j++ {
  84.             stack[i][j] = -1
  85.         }
  86.     }
  87.     return stack
  88. }
  89.  
  90. func Pop(stack [][]int) ([]int) {
  91.     for i:=len(stack)-1; i>=0; i-- {
  92.         //fmt.Println("!", i)
  93.         if stack[i][0] != -1 {
  94.             res := stack[i]
  95.             return res
  96.         }
  97.     }
  98.     return nil
  99. }
  100.  
  101. func contains(Q [][]int, zz []int) bool {
  102.     eq := true              //принадледжит
  103.     c:=0
  104.     for i:=0; i<len(Q); i++ {
  105.         for j:=0; j<len(Q); j++ {
  106.             //fmt.Println("zz = ", zz[j], " q = ", Q[i][j], " i = ", i)
  107.             if zz[j] == Q[i][j] {
  108.                 c++
  109.                 eq = true
  110.             } else {
  111.                 eq = false
  112.                 break
  113.             }
  114.             if c == len(Q) {
  115.                 return true
  116.             }
  117.         }
  118.         c = 0
  119.     }
  120.     return eq
  121. }
  122.  
  123. func Push(stack [][]int, what []int, size int) ([]int){
  124.     fmt.Println("inside size = ", size)
  125.     for i:=0; i<len(what); i++ {
  126.         stack[size][i] = what[i]
  127.     }
  128.     return stack[size]
  129. }
  130.  
  131. func Det(mas []Triplet, Final []int, q int) {
  132.     n := len(mas)
  133.     l := 1
  134.     lengt := 0
  135.     e:=make([]int, n)
  136.     for i:=0; i<n; i++ {
  137.         e[i] = -1
  138.     }
  139.     e[0] = q
  140.     qo := Closure(mas, e)
  141.     F := make([][]int, n, n)
  142.     for i:=0; i<n; i++ {
  143.         F[i] = make([]int, n)
  144.     }
  145.     for i:=0; i<n; i++ {
  146.         for j:=0; j<n; j++ {
  147.             F[i][j] = -1
  148.         }
  149.     }
  150.     delta := make([]Pair, n)
  151.     for i:=0; i<n; i++ {
  152.         delta[i].one = append(delta[i].one, -1)
  153.     }
  154.     Q := make([][]int, n, n)
  155.     for i:=0; i<n; i++ {
  156.         Q[i] = make([]int, n)
  157.     }
  158.     for i:=0; i<n; i++ {
  159.         for j:=0; j<n; j++ {
  160.             Q[i][j] = -1
  161.         }
  162.     }
  163.     for i:=0; i<len(qo); i++ {
  164.         Q[0][i] = qo[i]
  165.         //fmt.Println(Q[i])
  166.     }
  167.     stack := newStack(n*n)
  168.     for i:=0; i<len(qo); i++ {
  169.         stack[0][i] = qo[i]
  170.         //fmt.Println("st = ",stack[0][i])
  171.     }
  172.     lengt++
  173.     delta[0].one = qo
  174.     delta[0].two = "nune"
  175.     stackSize := 1
  176.     for stackSize > 0 {
  177.         fmt.Println("size = ", lengt)
  178.         z:= Pop(stack)
  179.         fmt.Println(stack)
  180.  
  181.         fmt.Println("z = ", z)
  182.         for u:=0; u<len(z); u++ {
  183.             if Final[u] == 1 {
  184.                 for i:=0; i<len(F); i++ {
  185.                     if F[i][0] != -1 {
  186.                         F[i] = z
  187.                         break
  188.                     }
  189.                 }
  190.                 break
  191.             }
  192.         }
  193.         VertexesOnLetter := make([]int, n)
  194.         for a:=0; a<n; a++ {
  195.             for i := 0; i < len(VertexesOnLetter); i++ {
  196.                 VertexesOnLetter[i] = -1
  197.             }
  198.             //fmt.Println("a = ", a)
  199.             letter := mas[a].third
  200.  
  201.             fmt.Println("letter = ", letter)
  202.             for i := 0; i < len(z); i++ {
  203.                 //fmt.Println("f = ", mas[i].first, " t = ", mas[i].third, " z = ", z[i], " l = ", letter)
  204.                 for j := 0; j < n; j++ {
  205.                     if mas[j].first == z[i] && mas[j].third == letter && !Search(VertexesOnLetter, mas[j].second) {
  206.                         for w := 0; w < len(VertexesOnLetter); w++ {
  207.                             if VertexesOnLetter[w] == -1 {
  208.                                 VertexesOnLetter[w] = mas[j].second
  209.                                 //fmt.Println("! = ", mas[j].second)
  210.                                 break
  211.                             }
  212.                         }
  213.                     }
  214.                 }
  215.             }
  216.  
  217.             fmt.Println("vL = ", VertexesOnLetter)
  218.  
  219.             zz := Closure(mas, VertexesOnLetter)
  220.  
  221.             //fmt.Println("zz!!zz = ", zz)
  222.             //fmt.Println("Q!!Q = ", Q)
  223.  
  224.             eq := contains(Q, zz)
  225.             //fmt.Println("! ", eq)
  226.             if !eq {
  227.                 //fmt.Println("in eq")
  228.                 for i := 0; i < len(Q); i++ {
  229.                     if Q[i][0] == -1 {
  230.                         Q[i] = zz
  231.                         break
  232.                     }
  233.                 }
  234.                 stackSize++
  235.                 lengt++
  236.                 Push(stack, zz, lengt)
  237.                 fmt.Println("size after push ", lengt)
  238.  
  239.                 if l < n && letter != "lambda"{
  240.                     delta[l].one = zz
  241.                     delta[l].two = letter
  242.                     l++
  243.                 }
  244.             }
  245.  
  246.         }
  247.         stackSize--
  248.     }
  249.     for i:=0; i<l; i++ {
  250.         for j:=0; j<l; j++ {
  251.             if delta[i].one[j] != -1 {
  252.                 fmt.Print(delta[i].one[j], " ")
  253.             }
  254.         }
  255.         fmt.Print(delta[i].two, " ")
  256.         fmt.Println()
  257.     }
  258.  
  259.  
  260. }
  261.  
  262. func main() {
  263.     var n, m, q int
  264.  
  265.     fmt.Scan(&n)
  266.     fmt.Scan(&m)
  267.  
  268.     mas := make([]Triplet, m)
  269.  
  270.     for i:=0; i<m; i++ {
  271.         fmt.Scan(&mas[i].first)
  272.         fmt.Scan(&mas[i].second)
  273.         fmt.Scan(&mas[i].third)
  274.     }
  275.  
  276.     final := make([]int, n)
  277.  
  278.     for i:=0; i<n; i++ {
  279.         fmt.Scan(&final[i])
  280.     }
  281.     fmt.Scan(&q)
  282.  
  283.     //PrintMe(mas, n, m, final)
  284.  
  285.     //C:= Closure(mas, n, z)
  286.     //fmt.Print("C = ",C)
  287.     Det(mas, final, q)
  288. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top