Kame3

Растојание во дрво - [дрво]

Jan 17th, 2021 (edited)
1,119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Растојание во дрво Problem 4 (0 / 0)
  2.  
  3. Дадено е пополнето дрво во кое секоја врска има тежина 2. За секој пар јазли потребно е да се најде најкраткото растојание меѓу нив. Доколку не постои решение испечатете "Error".
  4.  
  5. Име на класата (Java): NodeDistance.
  6.  
  7.  
  8. import java.io.BufferedReader;
  9. import java.io.InputStreamReader;
  10. import java.util.StringTokenizer;
  11. import java.util.NoSuchElementException;
  12.  
  13. class BNode<E> {
  14.    
  15.     public E info;
  16.     public BNode<E> left;
  17.     public BNode<E> right;
  18.    
  19.     static int LEFT = 1;
  20.     static int RIGHT = 2;
  21.    
  22.     public BNode(E info) {
  23.         this.info = info;
  24.         left = null;
  25.         right = null;
  26.     }
  27.    
  28.     public BNode() {
  29.         this.info = null;
  30.         left = null;
  31.         right = null;
  32.     }
  33.    
  34.     public BNode(E info, BNode<E> left, BNode<E> right) {
  35.         this.info = info;
  36.         this.left = left;
  37.         this.right = right;
  38.     }
  39.    
  40.     @Override
  41.     public String toString() {
  42.         return ""+info;
  43.     }
  44. }
  45.  
  46. class BTree<E> {
  47.    
  48.     public BNode<E> root;
  49.    
  50.     public BTree() {
  51.         root = null;
  52.     }
  53.    
  54.     public BTree(E info) {
  55.         root = new BNode<E>(info);
  56.     }
  57.    
  58.     public void makeRoot(E elem) {
  59.         root = new BNode(elem);
  60.     }
  61.    
  62.     public void makeRootNode(BNode<E> node) {
  63.         root = node;
  64.     }
  65.    
  66.     public BNode<E> addChild(BNode<E> node, int where, E elem) {
  67.        
  68.         BNode<E> tmp = new BNode<E>(elem);
  69.        
  70.         if (where == BNode.LEFT) {
  71.             if (node.left != null)  // veke postoi element
  72.                 return null;
  73.             node.left = tmp;
  74.         } else {
  75.             if (node.right != null) // veke postoi element
  76.                 return null;
  77.             node.right = tmp;
  78.         }
  79.        
  80.         return tmp;
  81.     }
  82.    
  83.     public BNode<E> addChildNode(BNode<E> node, int where, BNode<E> tmp) {
  84.        
  85.         if (where == BNode.LEFT) {
  86.             if (node.left != null)  // veke postoi element
  87.                 return null;
  88.             node.left = tmp;
  89.         } else {
  90.             if (node.right != null) // veke postoi element
  91.                 return null;
  92.             node.right = tmp;
  93.         }
  94.        
  95.         return tmp;
  96.     }
  97.    
  98.     private BNode<E> findNode(E x, BNode<E> root){
  99.         if(root == null)
  100.             return null;
  101.         if(root.info.equals(x))
  102.             return root;
  103.         else {
  104.             BNode<E> left = findNode(x,root.left);
  105.             if(left != null)
  106.                 return left;
  107.             else
  108.                 return findNode(x,root.right);
  109.         }
  110.     }
  111.    
  112.     public BNode<E> find(E x){
  113.         return findNode(x,root);
  114.     }
  115.    
  116.     public BNode<E> LCA(BNode<E> root, BNode<E> first, BNode<E> second){
  117.         if(root == null)
  118.             return null;
  119.         if(root == first || root == second)
  120.             return root;
  121.        
  122.         BNode<E> left = LCA(root.left, first,second);
  123.         BNode<E> right = LCA(root.right, first,second);
  124.         if(left != null && right != null)
  125.             return root;
  126.             if(left != null)
  127.                 return left;
  128.             else
  129.                 return right;
  130.     }
  131.    
  132.     public int distance(BNode<E> lca, BNode<E> node){
  133.         if(lca == null)
  134.             return 1000000;
  135.         if(lca == node)
  136.             return 0;
  137.         else
  138.             return Math.min((distance(lca.right,node)+1), (distance(lca.left,node)+1));
  139.     }
  140. }
  141.  
  142.  
  143.  
  144. interface Stack<E> {
  145.  
  146.     // Elementi na stekot se objekti od proizvolen tip.
  147.  
  148.     // Metodi za pristap:
  149.  
  150.     public boolean isEmpty ();
  151.         // Vrakja true ako i samo ako stekot e prazen.
  152.  
  153.     public E peek ();
  154.         // Go vrakja elementot na vrvot od stekot.
  155.  
  156.     // Metodi za transformacija:
  157.  
  158.     public void clear ();
  159.         // Go prazni stekot.
  160.  
  161.     public void push (E x);
  162.         // Go dodava x na vrvot na stekot.
  163.  
  164.     public E pop ();
  165.         // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
  166. }
  167.  
  168. class ArrayStack<E> implements Stack<E> {
  169.     private E[] elems;
  170.     private int depth;
  171.  
  172.     @SuppressWarnings("unchecked")
  173.     public ArrayStack (int maxDepth) {
  174.         // Konstrukcija na nov, prazen stek.
  175.         elems = (E[]) new Object[maxDepth];
  176.         depth = 0;
  177.     }
  178.  
  179.  
  180.     public boolean isEmpty () {
  181.         // Vrakja true ako i samo ako stekot e prazen.
  182.         return (depth == 0);
  183.     }
  184.  
  185.  
  186.     public E peek () {
  187.         // Go vrakja elementot na vrvot od stekot.
  188.         if (depth == 0)
  189.             throw new NoSuchElementException();
  190.         return elems[depth-1];
  191.     }
  192.  
  193.  
  194.     public void clear () {
  195.         // Go prazni stekot.
  196.         for (int i = 0; i < depth; i++)  elems[i] = null;
  197.         depth = 0;
  198.     }
  199.  
  200.  
  201.     public void push (E x) {
  202.         // Go dodava x na vrvot na stekot.
  203.         elems[depth++] = x;
  204.     }
  205.  
  206.  
  207.     public E pop () {
  208.         // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
  209.         if (depth == 0)
  210.             throw new NoSuchElementException();
  211.         E topmost = elems[--depth];
  212.         elems[depth] = null;
  213.         return topmost;
  214.     }
  215. }
  216.  
  217.  
  218.  
  219. public class NodeDistance {
  220.  
  221.     public static void main(String[] args) throws Exception {
  222.         int i, j, k;
  223.         int index;
  224.         String action;
  225.        
  226.         String line;
  227.  
  228.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  229.         StringTokenizer st;
  230.  
  231.         int N = Integer.parseInt(br.readLine());
  232.  
  233.         BNode<String> nodes[] = new BNode[N];
  234.         BTree<String> tree = new BTree<String>();
  235.        
  236.         for (i=0;i<N;i++)
  237.             nodes[i] = new BNode<String>();
  238.        
  239.         for (i = 0; i < N; i++) {
  240.             line = br.readLine();
  241.             st = new StringTokenizer(line);
  242.             index = Integer.parseInt(st.nextToken());
  243.             nodes[index].info = st.nextToken();
  244.             action = st.nextToken();
  245.             if (action.equals("LEFT")) {
  246.                 tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.LEFT, nodes[index]);
  247.             } else if (action.equals("RIGHT")) {
  248.                 tree.addChildNode(nodes[Integer.parseInt(st.nextToken())], BNode.RIGHT, nodes[index]);    
  249.             } else {
  250.                 // this node is the root
  251.                 tree.makeRootNode(nodes[index]);
  252.             }
  253.         }
  254.        
  255.        
  256.         int cases = Integer.parseInt(br.readLine());
  257.         for (int l = 0; l < cases; l++) {
  258.             String split[] = br.readLine().split(" +");
  259.             String from = split[0];
  260.             String to = split[1];
  261.            
  262.             // Vasiot kod ovde
  263.             BNode<String> f = tree.find(from);
  264.             BNode<String> t = tree.find(to);
  265.            
  266.             if(f == null || t == null){
  267.                 System.out.println("ERROR");
  268.                 continue;
  269.             }
  270.            
  271.             BNode<String> lca = tree.LCA(tree.root, f,t);
  272.            
  273.             System.out.println((tree.distance(lca,f) + tree.distance(lca,t))*2);
  274.            
  275.            
  276.         }
  277.         br.close();
  278.        
  279.        
  280.     }
  281.  
  282. }
  283.  
  284.  
  285. 8
  286. 0 A ROOT
  287. 1 B LEFT 0
  288. 2 C LEFT 1
  289. 3 D RIGHT 1
  290. 4 E RIGHT 0
  291. 5 F RIGHT 4
  292. 6 G LEFT 5
  293. 7 H RIGHT 5
  294. 3
  295. A D
  296. E E
  297. G Z
  298.  
  299. Sample output
  300.  
  301. 4
  302. 0
  303. ERROR
  304.  
  305.  
RAW Paste Data