API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 21st, 2018
67
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 8.89 KB | None | 0 0
raw download clone embed print report
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5. )
  6.  
  7. type Graph struct {
  8.     states       int
  9.     InputAlph    string
  10.     mark         string
  11.     newStates    int
  12.     newInputAlph string
  13.     parent string
  14.     depth int
  15. }
  16.  
  17. type Vert struct {
  18.     s    int
  19.     mark string
  20. }
  21.  
  22. func main() {
  23.  
  24.     var n, m, q int
  25.     //ind := 0
  26.     fmt.Scan(&n)
  27.     fmt.Scan(&m)
  28.     fmt.Scan(&q)
  29.  
  30.     arr1 := make([][] Graph, n, n)
  31.  
  32.     for i := 0; i < n; i++ {
  33.         arr1[i] = make([] Graph, m)
  34.     }
  35.  
  36.     for i := 0; i < n; i++ {
  37.         for j := 0; j < m; j++ {
  38.             fmt.Scan(&arr1[i][j].states)
  39.             //arr1[i][j].mark = "white"
  40.         }
  41.     }
  42.  
  43.     for i := 0; i < n; i++ {
  44.         for j := 0; j < m; j++ {
  45.             fmt.Scan(&arr1[i][j].InputAlph)
  46.         }
  47.     }
  48.     AufenkampHohn(arr1, n, m, q)
  49.     //DFS(arr1, n, m, q)
  50. }
  51.  
  52.  
  53. //2
  54. func print(arr1[][] Graph, n, m, q int) {
  55.  
  56.     fmt.Printf("digraph {\n")
  57.     fmt.Printf("    rankdir = LR\n")
  58.     fmt.Printf("    dummy [label = \"\", shape = none]\n")
  59.     for i := 0; i < n; i++ {
  60.         fmt.Printf("    %d ", i)
  61.         fmt.Printf("[shape = circle]\n")
  62.     }
  63.     fmt.Printf("    dummy -> 0\n")
  64.     //fmt.Printf("%d\n", q)
  65.     for i := 0; i < n; i++ {
  66.         for j := 0; j < m; j++ {
  67.             fmt.Printf("    %d -> %d [label = \"%c(%s)\"]\n", i, arr1[i][j].newStates, 97+j, arr1[i][j].newInputAlph)
  68.         }
  69.     }
  70.     fmt.Printf("}")
  71. }
  72. //
  73. func NewMatrix(arr1[][] Graph, arr[] Vert, newN, n, m, q int)  {
  74.     for i := 0; i < n; i++ {
  75.         for j := 0; j < m; j++ {
  76.             arr1[arr[i].s][j].newStates = arr[arr1[i][j].states].s
  77.             arr1[arr[i].s][j].newInputAlph = arr1[i][j].InputAlph
  78.         }
  79.     }
  80.     print(arr1, newN, m, q)
  81.  
  82. }
  83.  
  84. func DFS(arr1[][] Graph, n, m, q int) {
  85.     stack := newStack(n)
  86.     sizeStack := 0
  87.     arr := make([] Vert, n)
  88.     count := 0
  89.     stack[sizeStack] = q
  90.     sizeStack++
  91.     for sizeStack > 0 {
  92.         sizeStack--
  93.         v := stack[sizeStack]
  94.         if arr[v].mark != "black" {
  95.             arr[v].mark = "black"
  96.             arr[v].s = count
  97.             count++
  98.         }
  99.         for i := m - 1; i > -1; i-- {
  100.             u := arr1[v][i].states
  101.             if arr[u].mark != "black" {
  102.                 stack[sizeStack] = u
  103.                 sizeStack++
  104.             }
  105.         }
  106.     }
  107.     NewMatrix(arr1, arr, count, n, m, q)
  108. }
  109.  
  110. func newStack(n int) []int  {
  111.     stack := make([]int, n*n)
  112.     return stack
  113. }
  114.  
  115. type State struct {
  116.     order  int
  117.     depth  int
  118.     parent *State
  119. }
  120.  
  121. func newState(order int) *State {
  122.     s := &State{order: order, depth: 0}
  123.     s.parent = s
  124.     return s
  125. }
  126.  
  127. func find(v int, arr[] int) int {
  128.     if arr[v] == v {
  129.         return v
  130.     }
  131.     arr[v] = find(arr[v], arr)
  132.     return arr[v]
  133.  
  134. }
  135.  
  136. func unite(x, y int, arr[] int)  {
  137.     xx := find(x, arr)
  138.     yy := find(y, arr)
  139.     if xx == yy {
  140.         return
  141.     }
  142.     if xx != yy {
  143.         xx, yy = yy, xx
  144.     }
  145.     arr[xx] = yy
  146. }
  147.  
  148. func Split1(arr1[][] Graph, n, m int) (int ,[]int) {
  149.     var eq bool
  150.     M := n
  151.     pi := make([]int, n)
  152.     for i := 0; i < n; i++ {
  153.         pi[i] = i
  154.     }
  155.     for q1 := 0; q1 < n; q1++ {
  156.         for q2 := q1+1; q2 < n; q2++{
  157.             if find(q1, pi) != find(q2, pi){
  158.                 eq = true
  159.                 for x := 0; x < m; x++{
  160.                     if arr1[q1][x].InputAlph != arr1[q2][x].InputAlph {
  161.                         eq = false
  162.                         break
  163.                     }
  164.                 }
  165.                 if eq {
  166.                     unite(q1, q2, pi)
  167.                     M--
  168.                 }
  169.             }
  170.         }
  171.     }
  172.     for q := 0; q < n; q++ {
  173.         pi[q] = find(q, pi)
  174.     }
  175.     return M, pi
  176. }
  177.  
  178. func Split(arr1[][] Graph, pi[] int, n, m int) (int, []int) {
  179.     var eq bool
  180.     M := n
  181.     newPi := make([]int, n)
  182.     for i := 0; i < n; i++ {
  183.         newPi[i] = i
  184.     }
  185.     for q1 := 0; q1 < n; q1++ {
  186.         for q2 := q1 + 1; q2 < n; q2++ {
  187.             if (pi[q1] == pi[q2]) && (find(q1, newPi) != find(q2, newPi)) {
  188.                 eq = true
  189.                 for x := 0; x < m; x++ {
  190.                     w1 := arr1[q1][x].states
  191.                     w2 := arr1[q2][x].states
  192.                     if pi[w1] != pi[w2] {
  193.                         eq = false
  194.                         break
  195.                     }
  196.                 }
  197.                 if eq {
  198.                     unite(q1, q2, newPi)
  199.                     M--
  200.                 }
  201.             }
  202.         }
  203.     }
  204.     for q := 0; q < n; q++ {
  205.         pi[q] = find(q, newPi)
  206.     }
  207.     return M, pi
  208. }
  209.  
  210. func AufenkampHohn(arr1[][] Graph, n, m, qq int)  {
  211.  
  212.     M, pi := Split1(arr1, n, m)
  213.     var (
  214.         newM int
  215.         //newPi[] int
  216.     )
  217.     for  {
  218.         newM, pi = Split(arr1, pi, n, m)
  219.         if M == newM {
  220.             break
  221.         }
  222.         M = newM
  223.     }
  224.     /*count := 0
  225.     for i := 0; i < n; i++ {
  226.         if pi[i] < count {
  227.             continue
  228.         }
  229.         pi[i] = count
  230.         count++
  231.     }*/
  232.     arr := make([][] Graph, n, n)
  233.  
  234.     for i := 0; i < n; i++ {
  235.         arr[i] = make([] Graph, m)
  236.     }
  237.  
  238.     b := make([] bool, n)
  239.     for q := 0; q < n; q++ {
  240.         if newQ := pi[q]; !b[q] {
  241.             b[newQ] = true
  242.             for x := 0; x < m; x++ {
  243.                 arr[newQ][x].states = pi[arr1[q][x].states]
  244.                 arr[newQ][x].InputAlph = arr1[q][x].InputAlph
  245.             }
  246.         }
  247.     }
  248.     DFS(arr, n, m, pi[qq])
  249. }
  250.  
  251.  
  252.  
  253.  
  254. /*package main
  255.  
  256. import (
  257.     "fmt"
  258. )
  259.  
  260. type Graph struct {
  261.     states       int
  262.     InputAlph    string
  263.     mark         string
  264.     newStates    int
  265.     newInputAlph string
  266.     parent string
  267.     depth int
  268. }
  269.  
  270. type Vert struct {
  271.     s    int
  272.     mark string
  273. }
  274.  
  275. func main() {
  276.  
  277.     var n, m, q int
  278.     //ind := 0
  279.     fmt.Scan(&n)
  280.     fmt.Scan(&m)
  281.     fmt.Scan(&q)
  282.  
  283.     arr1 := make([][] Graph, n, n)
  284.  
  285.     for i := 0; i < n; i++ {
  286.         arr1[i] = make([] Graph, m)
  287.     }
  288.  
  289.     for i := 0; i < n; i++ {
  290.         for j := 0; j < m; j++ {
  291.             fmt.Scan(&arr1[i][j].states)
  292.             //arr1[i][j].mark = "white"
  293.         }
  294.     }
  295.  
  296.     for i := 0; i < n; i++ {
  297.         for j := 0; j < m; j++ {
  298.             fmt.Scan(&arr1[i][j].InputAlph)
  299.         }
  300.     }
  301.     AufenkampHohn(arr1, n, m, q)
  302.     //DFS(arr1, n, m, q)
  303. }
  304.  
  305.  
  306. //2
  307. func print(arr1[][] Graph, n, m, q int) {
  308.  
  309.     fmt.Printf("digraph {\n")
  310.     fmt.Printf("    rankdir = LR\n")
  311.     fmt.Printf("    dummy [label = \"\", shape = none]\n")
  312.     for i := 0; i < n; i++ {
  313.         fmt.Printf("    %d ", i)
  314.         fmt.Printf("[shape = circle]\n")
  315.     }
  316.     fmt.Printf("    dummy -> ")
  317.     fmt.Printf("%d\n", q)
  318.     for i := 0; i < n; i++ {
  319.         for j := 0; j < m; j++ {
  320.             fmt.Printf("    %d -> %d [label = \"%c(%s)\"]\n", i, arr1[i][j].newStates, 97+j, arr1[i][j].newInputAlph)
  321.         }
  322.     }
  323.     fmt.Printf("}")
  324. }
  325. //
  326. func NewMatrix(arr1[][] Graph, arr[] Vert, newN, n, m, q int)  {
  327.     for i := 0; i < n; i++ {
  328.         for j := 0; j < m; j++ {
  329.             arr1[arr[i].s][j].newStates = arr[arr1[i][j].states].s
  330.             arr1[arr[i].s][j].newInputAlph = arr1[i][j].InputAlph
  331.         }
  332.     }
  333.     print(arr1, newN, m, q)
  334.  
  335. }
  336.  
  337. func DFS(arr1[][] Graph, n, m, q int) {
  338.     stack := newStack(n)
  339.     sizeStack := 0
  340.     arr := make([] Vert, n)
  341.     count := 0
  342.     stack[sizeStack] = q
  343.     sizeStack++
  344.     for sizeStack > 0 {
  345.         sizeStack--
  346.         v := stack[sizeStack]
  347.         if arr[v].mark != "black" {
  348.             arr[v].mark = "black"
  349.             arr[v].s = count
  350.             count++
  351.         }
  352.         for i := m - 1; i >= 0; i-- {
  353.             u := arr1[v][i].states
  354.             //fmt.Println(u)
  355.             if arr[u].mark != "black" {
  356.                 stack[sizeStack] = u
  357.                 sizeStack++
  358.             }
  359.         }
  360.     }
  361.     NewMatrix(arr1, arr, count, n, m, q)
  362. }
  363.  
  364. func newStack(n int) []int  {
  365.     stack := make([]int, n*n)
  366.     return stack
  367. }
  368.  
  369. type State struct {
  370.     order  int
  371.     depth  int
  372.     parent *State
  373. }
  374.  
  375. func newState(order int) *State {
  376.     s := &State{order: order, depth: 0}
  377.     s.parent = s
  378.     return s
  379. }
  380.  
  381. func union(s *State, state *State) {
  382.     root1, root2 := find(s), find(state)
  383.     if root1.depth < root2.depth {
  384.         root1.parent = root2
  385.     } else {
  386.         root2.parent = root1
  387.         if root1.depth == root2.depth && root1 != root2 {
  388.             root1.depth++
  389.         }
  390.     }
  391. }
  392.  
  393. func (s *State) equivalent(state *State) bool {
  394.     return find(s) == find(state)
  395. }
  396.  
  397. func find(s *State) *State {
  398.     if s.parent == s {
  399.         return s
  400.     }
  401.     s.parent = find(s.parent)
  402.     return s.parent
  403. }
  404.  
  405. func Split1(arr1[][] Graph, n, m, q int) (int, []int) {
  406.     pi := make([] int, n)
  407.     M := n
  408.     newPi := make([] State, n)
  409.     for i := 0; i < n; i++ {
  410.         newPi[i] = *newState(i)
  411.     }
  412.     for q1 := 0; q1 < n; q1++ {
  413.         for q2 := 0; q2 < n; q2++ {
  414.             if find(&newPi[q1]) != find(&newPi[q2]) {
  415.                 eq := true
  416.                 for x := 0; x < m; x++ {
  417.                     if arr1[q1][x].InputAlph != arr1[q2][x].InputAlph {
  418.                         eq = false
  419.                         break
  420.                     }
  421.                 }
  422.                 if eq {
  423.                     union(&newPi[q1], &newPi[q2])
  424.                     M--
  425.                 }
  426.             }
  427.         }
  428.     }
  429.     for q := 0; q < n; q++ {
  430.         pi[q] = find(&newPi[q]).order
  431.     }
  432.     return M, pi
  433. }
  434.  
  435. func Split(arr1[][] Graph, pi[] int, n, m, q int) (int, []int) {
  436.     M := n
  437.     newPi := make([] State, n)
  438.     for i := 0; i < n; i++ {
  439.         newPi[i] = *newState(i)
  440.     }
  441.     for q1 := 0; q1 < n; q1++ {
  442.         for q2 := 0; q2 < n; q2++ {
  443.             if pi[newPi[q1].order] == pi[newPi[q2].order] && !newPi[q1].equivalent(&newPi[q2]) {
  444.                 eq := true
  445.                 for x := 0; x < m; x++ {
  446.                     w1 := arr1[newPi[q1].order][x].states
  447.                     w2 := arr1[newPi[q2].order][x].states
  448.                     if pi[w1] != pi[w2] {
  449.                         eq = false
  450.                         break
  451.                     }
  452.                 }
  453.                 if eq {
  454.                     union(&newPi[q1], &newPi[q2])
  455.                     M--
  456.                 }
  457.             }
  458.         }
  459.     }
  460.     for i := range pi {
  461.         pi[newPi[i].order] = find(&newPi[i]).order
  462.     }
  463.     return M, pi
  464. }
  465.  
  466. func AufenkampHohn(arr1[][] Graph, n, m, qq int) {
  467.     M, pi := Split1(arr1, n, m, qq)
  468.     var newM int
  469.     newM, pi = Split(arr1, pi, n, m, qq)
  470.     if M != newM {
  471.         M = newM
  472.     }
  473.  
  474.     arr := make([][] Graph, n, n)
  475.     for i := 0; i < n; i++ {
  476.         arr[i] = make([] Graph, m)
  477.     }
  478.  
  479.     b := make([] bool, n)
  480.     for q := 0; q < n; q++ {
  481.         if newQ := pi[q]; !b[newQ] {
  482.             b[newQ] = true
  483.             for x := 0; x < m; x++ {
  484.                 arr[newQ][x].states = pi[arr1[q][x].states]
  485.                 arr[newQ][x].InputAlph = arr1[q][x].InputAlph
  486.             }
  487.         }
  488.     }
  489.     //fmt.Println(M)
  490.     print(arr, M, m, qq)
  491.     DFS(arr, n, m, pi[qq])
  492. }*/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!