daily pastebin goal
57%
SHARE
TWEET

Сасному человеку

a guest Jun 3rd, 2018 49 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.     e:=make([]int, n)
  135.     for i:=0; i<n; i++ {
  136.         e[i] = -1
  137.     }
  138.     e[0] = q
  139.     qo := Closure(mas, e)
  140.     F := make([][]int, n, n)
  141.     for i:=0; i<n; i++ {
  142.         F[i] = make([]int, n)
  143.     }
  144.     for i:=0; i<n; i++ {
  145.         for j:=0; j<n; j++ {
  146.             F[i][j] = -1
  147.         }
  148.     }
  149.     delta := make([]Pair, n)
  150.     for i:=0; i<n; i++ {
  151.         delta[i].one = append(delta[i].one, -1)
  152.     }
  153.     Q := make([][]int, n, n)
  154.     for i:=0; i<n; i++ {
  155.         Q[i] = make([]int, n)
  156.     }
  157.     for i:=0; i<n; i++ {
  158.         for j:=0; j<n; j++ {
  159.             Q[i][j] = -1
  160.         }
  161.     }
  162.     for i:=0; i<len(qo); i++ {
  163.         Q[0][i] = qo[i]
  164.         //fmt.Println(Q[i])
  165.     }
  166.     stack := newStack(n*n)
  167.     for i:=0; i<len(qo); i++ {
  168.         stack[0][i] = qo[i]
  169.         //fmt.Println("st = ",stack[0][i])
  170.     }
  171.     delta[0].one = qo
  172.     delta[0].two = "nune"
  173.     stackSize := 1
  174.     for stackSize > 0 {
  175.         fmt.Println("size = ", stackSize)
  176.         z:= Pop(stack)
  177.         fmt.Println(stack)
  178.  
  179.         fmt.Println("z = ", z)
  180.         for u:=0; u<len(z); u++ {
  181.             if Final[u] == 1 {
  182.                 for i:=0; i<len(F); i++ {
  183.                     if F[i][0] != -1 {
  184.                         F[i] = z
  185.                         break
  186.                     }
  187.                 }
  188.                 break
  189.             }
  190.         }
  191.         VertexesOnLetter := make([]int, n)
  192.         for a:=0; a<n; a++ {
  193.             for i := 0; i < len(VertexesOnLetter); i++ {
  194.                 VertexesOnLetter[i] = -1
  195.             }
  196.             //fmt.Println("a = ", a)
  197.             letter := mas[a].third
  198.  
  199.             fmt.Println("letter = ", letter)
  200.             for i := 0; i < len(z); i++ {
  201.                 //fmt.Println("f = ", mas[i].first, " t = ", mas[i].third, " z = ", z[i], " l = ", letter)
  202.                 for j := 0; j < n; j++ {
  203.                     if mas[j].first == z[i] && mas[j].third == letter && !Search(VertexesOnLetter, mas[j].second) {
  204.                         for w := 0; w < len(VertexesOnLetter); w++ {
  205.                             if VertexesOnLetter[w] == -1 {
  206.                                 VertexesOnLetter[w] = mas[j].second
  207.                                 //fmt.Println("! = ", mas[j].second)
  208.                                 break
  209.                             }
  210.                         }
  211.                     }
  212.                 }
  213.             }
  214.  
  215.             fmt.Println("vL = ", VertexesOnLetter)
  216.  
  217.             zz := Closure(mas, VertexesOnLetter)
  218.  
  219.             //fmt.Println("zz!!zz = ", zz)
  220.             //fmt.Println("Q!!Q = ", Q)
  221.  
  222.             eq := contains(Q, zz)
  223.             //fmt.Println("! ", eq)
  224.             if !eq {
  225.                 //fmt.Println("in eq")
  226.                 for i := 0; i < len(Q); i++ {
  227.                     if Q[i][0] == -1 {
  228.                         Q[i] = zz
  229.                         break
  230.                     }
  231.                 }
  232.                 stackSize++
  233.                 Push(stack, zz, stackSize)
  234.  
  235.                 if l < n && letter != "lambda"{
  236.                     delta[l].one = zz
  237.                     delta[l].two = letter
  238.                     l++
  239.                 }
  240.             }
  241.  
  242.         }
  243.         stackSize--
  244.     }
  245.     for i:=0; i<l; i++ {
  246.         for j:=0; j<l; j++ {
  247.             if delta[i].one[j] != -1 {
  248.                 fmt.Print(delta[i].one[j], " ")
  249.             }
  250.         }
  251.         fmt.Print(delta[i].two, " ")
  252.         fmt.Println()
  253.     }
  254.  
  255.  
  256. }
  257.  
  258. func main() {
  259.     var n, m, q int
  260.  
  261.     fmt.Scan(&n)
  262.     fmt.Scan(&m)
  263.  
  264.     mas := make([]Triplet, m)
  265.  
  266.     for i:=0; i<m; i++ {
  267.         fmt.Scan(&mas[i].first)
  268.         fmt.Scan(&mas[i].second)
  269.         fmt.Scan(&mas[i].third)
  270.     }
  271.  
  272.     final := make([]int, n)
  273.  
  274.     for i:=0; i<n; i++ {
  275.         fmt.Scan(&final[i])
  276.     }
  277.     fmt.Scan(&q)
  278.  
  279.     //PrintMe(mas, n, m, final)
  280.  
  281.     //C:= Closure(mas, n, z)
  282.     //fmt.Print("C = ",C)
  283.     Det(mas, final, q)
  284. }
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