SHARE
TWEET

Untitled

a guest May 19th, 2019 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. var pos int
  6.  
  7. type Vertex struct {
  8.     mark, pos, number, depth, parent *int
  9.     next []int
  10.     signals []string
  11. }
  12.  
  13. func union(x, y int, delta []Vertex) {
  14.     rootx := find(x, delta)
  15.     rooty := find(y, delta)
  16.     if *delta[rootx].depth < *delta[rooty].depth {
  17.         *delta[rootx].parent = *delta[rooty].number
  18.     } else {
  19.         *delta[rooty].parent = rootx
  20.         if *delta[rootx].depth == *delta[rooty].depth && rootx != rooty {
  21.             *delta[rootx].depth++
  22.         }
  23.     }
  24. }
  25.  
  26. func find(v int, delta []Vertex) int {
  27.     if v == *delta[*delta[v].parent].number {
  28.         return v
  29.     }
  30.     *delta[v].parent = find(*delta[v].parent, delta)
  31.     return *delta[v].parent
  32. }
  33.  
  34. func VV(pos int, Delta []int, delta []Vertex, res []Vertex, Len int) {
  35.     is := false
  36.     var i int
  37.     for i = 0; i < Len; i++ {
  38.         if pos == Delta[i] {
  39.             is = true
  40.             break
  41.         }
  42.     }
  43.     if is {
  44.         v := delta[i]
  45.         *v.mark = 1
  46.         *v.pos = pos
  47.         res[pos] = v
  48.         pos++
  49.         for _, x := range v.next {
  50.             u := delta[x]
  51.             if *u.mark == 0 && *v.number != *u.number {
  52.                 VV(*u.number, Delta, delta, res, Len)
  53.             }
  54.         }
  55.         *v.mark = 2
  56.     }
  57. }
  58.  
  59. func main() {
  60.     var n, m, q0, i, j, k int
  61.     pos = 0
  62.     fmt.Scanf("%d\n%d\n%d\n", &n, &m, &q0)
  63.     min := n
  64.     delta := make([]Vertex, n)
  65.     for i = 0; i < n; i++ {
  66.         delta[i] = Vertex{new(int), new(int), new(int), new(int), new(int), make([]int, m), make([]string, m)}
  67.         *delta[i].parent = i
  68.         *delta[i].depth = 0
  69.         *delta[i].mark = 0
  70.         *delta[i].pos = 0
  71.         *delta[i].number = i
  72.         for j = 0; j < m; j++ {
  73.             fmt.Scan(&delta[i].next[j])
  74.         }
  75.     }
  76.     for i = 0; i < n; i++ {
  77.         for j = 0; j < m; j++ {
  78.             fmt.Scan(&delta[i].signals[j])
  79.         }
  80.     }
  81.     //SPLIT1---------------------------------
  82.     pi := make([]int, n)
  83.     for i = 0; i < n; i++ {
  84.         for j = i + 1; j < n; j++ {
  85.             if find(i, delta) != find(j, delta) {
  86.                 eq := true
  87.                 for k = 0; k < m; k++ {
  88.                     if delta[i].signals[k] != delta[j].signals[k] {
  89.                         eq = false
  90.                         break
  91.                     }
  92.                 }
  93.                 if eq {
  94.                     union(i, j, delta)
  95.                     //fmt.Println(*delta[i].parent, *delta[j].parent)
  96.                     min--
  97.                 }
  98.             }
  99.         }
  100.     }
  101.     for i = 0; i < n; i++ {
  102.         pi[i] = find(i, delta)
  103.     }
  104.     //---------------------------
  105.     for {
  106.         //SPLIT-----------------
  107.         min = n
  108.         for i = 0; i < n; i++ {
  109.             *delta[i].parent = i
  110.             *delta[i].depth = 0
  111.         }
  112.         for i = 0; i < n; i++ {
  113.             for j = i + 1; j < n; j++ {
  114.                 a := find(i, delta)
  115.                 b := find(j, delta)
  116.                 if pi[i] == pi[j] && a != b {
  117.                     eq := true
  118.                     for k = 0; k < m; k++ {
  119.                         w1 := delta[i].next[k]
  120.                         w2 := delta[j].next[k]
  121.                         if pi[w1] != pi[w2] {
  122.                             eq = false
  123.                             break
  124.                         }
  125.                     }
  126.                     if eq {
  127.                         union(i, j, delta)
  128.                         min--
  129.                     }
  130.                 }
  131.             }
  132.         }
  133.         for i = 0; i < n; i++ {
  134.             pi[i] = find(i, delta)
  135.             fmt.Println(pi)
  136.         }
  137.         //----------------------
  138.         if min == n {
  139.             break
  140.         }
  141.     }
  142.     //--------------------------
  143.     Len := 0
  144.     Delta := make([]int, n)
  145.     for i = 0; i < n; i++ {
  146.         q := pi[i]
  147.         is := true
  148.         for j = 0; j < Len; j++ {
  149.             if q == Delta[j] {
  150.                 is = false
  151.                 break
  152.             }
  153.         }
  154.         if is {
  155.             Delta[Len] = q
  156.             Len++
  157.         }
  158.     }
  159.  
  160.     res := make([]Vertex, Len)
  161.     VV(q0, Delta, delta, res, Len)
  162.  
  163.     fmt.Printf("digraph {\n\trankdir = LR\n\tdummy [label = \"\", shape = none]\n")
  164.     for i = 0; i < Len; i++ {
  165.         fmt.Printf("\t%d [shape = circle]\n", *res[i].number)
  166.     }
  167.     fmt.Printf("\tdummy -> %d\n", 0)
  168.     for i = 0; i < Len; i++ {
  169.         for j = 0; j < m; j++ {
  170.             fmt.Printf("\t%d -> %d [label = \"%c(%s)\"]\n", i, res[i].next[j], 97 + j, res[i].signals[j])
  171.         }
  172.     }
  173.     fmt.Printf("}\n")
  174. }
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