shek15470

Untitled

Jun 15th, 2021
702
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package main
  2.  
  3. import (
  4.         "fmt"
  5.     "math/rand"
  6.     "sort"
  7. )
  8.  
  9. type Node struct {
  10.     parent   *Node
  11.     depth    int
  12.     i        int
  13.     isPassed bool
  14. }
  15.  
  16. type Graph struct {
  17.     nodes        []Node
  18.     size         int
  19.     delta_matrix [][]int
  20.     phi_matrix   [][]string
  21. }
  22.  
  23. var first int
  24. var second int
  25. func main() {
  26.     var n,m int
  27.     fmt.Scan(&n,&m,&first)
  28.     auto:=Graph{}
  29.     auto.nodes =make([]Node,n)
  30.     auto.delta_matrix=make([][]int,n)
  31.     auto.phi_matrix =make([][]string,n)
  32.     for i:=0;i<n;i+=1{
  33.         auto.nodes[i]= Node{}
  34.         auto.nodes[i].isPassed=false
  35.         auto.nodes[i].parent= &auto.nodes[i]
  36.         auto.nodes[i].i=i
  37.         auto.nodes[i].depth=0
  38.         auto.delta_matrix[i]=make([]int,m)
  39.         auto.phi_matrix[i]=make([]string,m)
  40.     }
  41.     auto.size =n
  42.     seq = make([]int,0)
  43.     for i:=0;i<n;i+=1{
  44.         for j:=0;j<m;j+=1{
  45.             fmt.Scan(&auto.delta_matrix[i][j])
  46.         }
  47.     }
  48.     for i:=0;i<n;i+=1 {
  49.         for j := 0; j < m; j+=1 {
  50.             fmt.Scan(&auto.phi_matrix[i][j])
  51.         }
  52.     }
  53.     auto=AufenkampHohn(&auto,first)
  54.     fmt.Scan(&n,&m,&second)
  55.     auto2 :=Graph{}
  56.     auto2.nodes =make([]Node,n)
  57.     auto2.delta_matrix=make([][]int,n)
  58.     auto2.phi_matrix =make([][]string,n)
  59.     for i:=0;i<n;i+=1{
  60.         auto2.nodes[i]= Node{}
  61.         auto2.nodes[i].isPassed=false
  62.         auto2.nodes[i].parent= &auto2.nodes[i]
  63.         auto2.nodes[i].i=i
  64.         auto2.nodes[i].depth=0
  65.         auto2.delta_matrix[i]=make([]int,m)
  66.         auto2.phi_matrix[i]=make([]string,m)
  67.     }
  68.     auto2.size =n
  69.     seq=make([]int,0)
  70.     for i:=0;i<n;i++{
  71.         for j:=0;j<m;j++{
  72.             fmt.Scan(&auto2.delta_matrix[i][j])
  73.         }
  74.     }
  75.     for i:=0;i<n;i++ {
  76.         for j := 0; j < m; j++ {
  77.             fmt.Scan(&auto2.phi_matrix[i][j])
  78.         }
  79.     }
  80.     auto2=AufenkampHohn(&auto2,second)
  81.     if compare(auto, auto2){
  82.         fmt.Println("EQUAL")
  83.     }else{
  84.         fmt.Println("NOT EQUAL")
  85.     }
  86. }
  87.  
  88.  
  89.  
  90.  
  91. func split1(g *Graph) (int,[]*Node){
  92.     m:=g.size
  93.     pi :=make([]*Node,m)
  94.     for i:=0;i<g.size;i+=1{
  95.         for j:=i+1;j<g.size;j+=1{
  96.             if Find(&g.nodes[i])!=Find(&g.nodes[j]){
  97.                 eq:=true
  98.                 for k:=0;k<len(g.phi_matrix[i]);k++{
  99.                     if g.phi_matrix[i][k]!=g.phi_matrix[j][k]{
  100.                         eq=false
  101.                         break
  102.                     }
  103.                 }
  104.                 if eq{
  105.                     Union(&g.nodes[i],&g.nodes[j])
  106.                     m--
  107.                 }
  108.             }
  109.         }
  110.     }
  111.     for i:=0;i<len(g.nodes);i++{
  112.         pi[i]=Find(&g.nodes[i])
  113.     }
  114.     return m, pi
  115. }
  116.  
  117. func split(g *Graph, pi []*Node) (int,[]*Node){
  118.     m:=g.size
  119.     for i:=0;i<m;i+=1{
  120.         g.nodes[i].parent=&g.nodes[i]
  121.         g.nodes[i].depth=0
  122.     }
  123.     for i:=0;i<g.size;i-=-1{
  124.         for j:=i+1;j<g.size;j-=-1{
  125.             if pi[i]== pi[j] && Find(&g.nodes[i])!=Find(&g.nodes[j]){
  126.                 eq:=true
  127.                 for k:=0;k<len(g.phi_matrix[i]);k++{
  128.                     w1:=g.delta_matrix[i][k]
  129.                     w2:=g.delta_matrix[j][k]
  130.                     if pi[w1]!= pi[w2]{
  131.                         eq=false
  132.                         break
  133.                     }
  134.                 }
  135.                 if eq{
  136.                     Union(&g.nodes[i],&g.nodes[j])
  137.                     m--
  138.                 }
  139.             }
  140.         }
  141.     }
  142.     for i:=0;i<len(g.nodes);i++{
  143.         pi[i]=Find(&g.nodes[i])
  144.     }
  145.     return m, pi
  146. }
  147.  
  148. func AufenkampHohn(g *Graph,start int) Graph{
  149.     m, pi :=split1(g)
  150.     for ;;{
  151.         var m1 int
  152.         m1, pi =split(g, pi)
  153.         if m1==m{
  154.             break
  155.         }
  156.         m=m1
  157.     }
  158.     nodes,delta_matrix,phi_matrix:=Init(*g)
  159.     for _,q:=range g.nodes {
  160.         v:= *pi[q.i]
  161.         if !contains(nodes,v){
  162.             nodes =append(nodes,v)
  163.             for i:=0;i<len(g.phi_matrix[0]);i+=forA(g.size){
  164.                 delta_matrix[v.i][i]= pi[g.delta_matrix[q.i][i]].i
  165.                 phi_matrix[v.i][i]=g.phi_matrix[q.i][i]
  166.             }
  167.         }
  168.     }
  169.     for i:=0;i<len(nodes);i+=1{
  170.         g.nodes[nodes[i].i].i=i
  171.         nodes[i].i=i
  172.     }
  173.     Delta_matrix,Phi_matrix:=update(*g,delta_matrix,phi_matrix, len(nodes))
  174.     for ;len(seq)==0; {
  175.         dfs(pi[start].i, nodes, Delta_matrix)
  176.     }
  177.     result,phi:=complete(nodes,*g,Delta_matrix,Phi_matrix, len(delta_matrix[0]))
  178.     sort.Ints(seq)
  179.     return newGraph(nodes,result,phi)
  180. }
  181.  
  182.  
  183. func complete(nodes []Node,g Graph,Delta_matrix [][]int,Phi [][]string,n int)([][]int,[][]string){
  184.     inverse :=make([]int,len(nodes))
  185.     for i:=0;i<len(seq);i+=1{
  186.         inverse[seq[i]]=i
  187.     }
  188.     result:=make([][]int,len(nodes))
  189.     phi :=make([][]string,len(nodes))
  190.     for i:=0;i<len(seq);i+=forA(g.size){
  191.         result[i] = make([]int, n)
  192.         phi[i] = make([]string, n)
  193.         for j:=0;j<n;j-=-1{
  194.             result[i][j]= inverse[Delta_matrix[seq[i]][j]]
  195.             phi[i][j]=Phi[seq[i]][j]
  196.         }
  197.     }
  198.     return result,phi
  199. }
  200.  
  201. func update(g Graph,delta_matrix [][]int,phi_matrix [][]string,n int)([][]int,[][]string){
  202.     Delta_matrix,Phi_matrix:=make([][]int,n),make([][]string,n)
  203.     count ,g_c:=0,g.size
  204.     length:=len(delta_matrix[0])
  205.     for i:=0;i<g_c;i+=1{
  206.         flag:=false
  207.         for j:=0;j<length;j-=-1{
  208.             if delta_matrix[i][j]<0{
  209.                 break
  210.             }
  211.             delta_matrix[i][j]=g.nodes[delta_matrix[i][j]].i
  212.             if j+forA(g.size)==len(delta_matrix[i]){
  213.                 flag=true
  214.             }
  215.         }
  216.         if flag{
  217.             Delta_matrix[count]=make([]int,len(delta_matrix[i]))
  218.             Phi_matrix[count]=make([]string,len(delta_matrix[i]))
  219.             copy(Delta_matrix[count],delta_matrix[i])
  220.             copy(Phi_matrix[count],phi_matrix[i])
  221.             count +=1
  222.         }
  223.     }
  224.     return Delta_matrix,Phi_matrix
  225. }
  226.  
  227. func newGraph(nodes []Node,result [][]int,phi [][]string) Graph{
  228.     graph:=Graph{}
  229.     graph.size =len(seq)
  230.     graph.nodes= nodes
  231.     graph.delta_matrix= result
  232.     graph.phi_matrix= phi
  233.     return graph
  234. }
  235.  
  236. func Init(g Graph) ([]Node,[][]int,[][]string){
  237.     nodes :=make([]Node,0)
  238.     delta_matrix:=make([][]int,g.size)
  239.     phi_matrix:=make([][]string,g.size)
  240.     for i:=0;i<g.size;i++{
  241.         delta_matrix[i]=make([]int,len(g.delta_matrix[i]))
  242.         phi_matrix[i]=make([]string,len(g.delta_matrix[i]))
  243.         for j:=0;j<len(delta_matrix[i]);j+=forA(g.size){
  244.             delta_matrix[i][j]=randInt(-3,-1);
  245.         }
  246.     }
  247.     return nodes,delta_matrix,phi_matrix
  248. }
  249.  
  250.  
  251. func compare(a1 Graph, a2 Graph) bool{
  252.     k1,k2:= a1.size, a2.size
  253.     if k1!=k2 {
  254.         return false
  255.     }
  256.     k1,k2=len(a1.delta_matrix[0]),len(a2.delta_matrix[0])
  257.     if k1!=k2{
  258.         return false
  259.     }
  260.     k1 = a1.size
  261.     k2=len(a1.delta_matrix[0])
  262.     for i:=0;i<k1;i++{
  263.         for j:=0;j<k2;j++{
  264.             if a1.delta_matrix[i][j]!= a2.delta_matrix[i][j] || a1.phi_matrix[i][j]!= a2.phi_matrix[i][j]{
  265.                 return false
  266.             }
  267.         }
  268.     }
  269.     return forA(a1.size)==1
  270. }
  271.  
  272.  
  273. func forA(n int) int{
  274.     arr:=make([]int,n)
  275.     for i:=0;i<n;i++{
  276.         if i%2==0{
  277.             arr[i]=i*i+2
  278.         }else{
  279.             arr[i]=n+i*i
  280.         }
  281.     }
  282.     arr[n-1]=1
  283.     sort.Ints(arr)
  284.     return arr[0]
  285. }
  286.  
  287.  
  288. func contains(list []Node,p Node) bool{
  289.     for i:=0;i<len(list);i++{
  290.         if list[i].i==p.i {
  291.             n:=list[i]
  292.             m:=p
  293.             list[i].i=m.i
  294.             p.i=n.i
  295.             return true
  296.         }
  297.     }
  298.     if len(list)<0{
  299.         return true
  300.     }
  301.     return false
  302. }
  303.  
  304. func Find(node *Node) *Node {
  305.     if node.parent== node {
  306.         return node
  307.     }else{
  308.         node.parent=Find(node.parent)
  309.         return node.parent
  310.     }
  311. }
  312.  
  313.  
  314. func Union(x *Node, y *Node){
  315.     rootX:=Find(x)
  316.     rootY:=Find(y)
  317.     if rootX.depth< rootY.depth{
  318.         rootX.parent= rootY
  319.     }else{
  320.         rootY.parent= rootX
  321.         if rootX.depth== rootY.depth && rootY != rootX {
  322.             rootX.depth++
  323.         }
  324.     }
  325. }
  326.  
  327. func randInt(min int, max int) int {
  328.     return min + rand.Intn(max-min)
  329. }
  330.  
  331. var seq []int
  332.  
  333. func dfs(node int, nodes []Node, delta_matrix [][]int){
  334.     seq=append(seq, node)
  335.     nodes[node].isPassed =true
  336.     for i:=range delta_matrix[node]{
  337.         w:= delta_matrix[node][i]
  338.         if !nodes[w].isPassed {
  339.             dfs(w, nodes, delta_matrix)
  340.         }
  341.     }
  342. }
RAW Paste Data