Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package zad4;
- import java.io.BufferedReader;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- import java.util.StringTokenizer;
- import java.util.NoSuchElementException;
- class BNode<E> {
- public E info;
- public BNode<E> left;
- public BNode<E> right;
- static int LEFT = 1;
- static int RIGHT = 2;
- public BNode(E info) {
- this.info = info;
- left = null;
- right = null;
- }
- public BNode() {
- this.info = null;
- left = null;
- right = null;
- }
- public BNode(E info, BNode<E> left, BNode<E> right) {
- this.info = info;
- this.left = left;
- this.right = right;
- }
- @Override
- public String toString() {
- return "" + info;
- }
- }
- class BTree<E> {
- public BNode<E> root;
- public BTree() {
- root = null;
- }
- public BTree(E info) {
- root = new BNode<E>(info);
- }
- public void makeRoot(E elem) {
- root = new BNode(elem);
- }
- public void makeRootNode(BNode<E> node) {
- root = node;
- }
- public BNode<E> addChild(BNode<E> node, int where, E elem) {
- BNode<E> tmp = new BNode<E>(elem);
- if (where == BNode.LEFT) {
- if (node.left != null) // veke postoi element
- return null;
- node.left = tmp;
- } else {
- if (node.right != null) // veke postoi element
- return null;
- node.right = tmp;
- }
- return tmp;
- }
- public BNode<E> addChildNode(BNode<E> node, int where, BNode<E> tmp) {
- if (where == BNode.LEFT) {
- if (node.left != null) // veke postoi element
- return null;
- node.left = tmp;
- } else {
- if (node.right != null) // veke postoi element
- return null;
- node.right = tmp;
- }
- return tmp;
- }
- public BNode<E> getNode(E x) {
- return getNode(this.root, x);
- }
- private BNode<E> getNode(BNode<E> r, E x) {
- if (r == null) {
- return null;
- }
- if (r.info.equals(x)) {
- return r;
- }
- BNode<E> a = getNode(r.left, x);
- BNode<E> b = getNode(r.right, x);
- if (a != null) {
- return a;
- } else {
- return b;
- }
- }
- public BNode<E> getParent(BNode<E> node) {
- return getParent(this.root, node);
- }
- private BNode<E> getParent(BNode<E> n, BNode<E> node) {
- if (n == null) {
- return null;
- }
- if (n.left == null && n.right == null) {
- return null;
- }
- if (n.left == node || n.right == node) {
- return n;
- }
- BNode<E> a = getParent(n.left, node);
- BNode<E> b = getParent(n.right, node);
- if (a != null) {
- return a;
- } else {
- return b;
- }
- }
- public int isUnder(BNode<E> node, BNode<E> gorno) {
- int l = 0;
- if (node == gorno) {
- return 0;
- }
- if (getParent(node) == gorno) {
- return 2;
- }
- while (node != gorno) {
- node = getParent(node);
- l += 2;
- if (node == this.root) {
- return -1;
- }
- }
- return l;
- }
- public BNode<E> findCommonRoot(BNode<E> n1, BNode<E> n2) {
- return findCommonRoot(this.root, n1, n2);
- }
- private BNode<E> findCommonRoot(BNode<E> root, BNode<E> n1, BNode<E> n2) {
- if (isUnder(n1, root.left) > 0 && isUnder(n2, root.left) > 0) {
- return findCommonRoot(root.left, n1, n2);
- } else if (isUnder(n1, root.right) > 0 && isUnder(n2, root.right) > 0) {
- return findCommonRoot(root.right, n1, n2);
- } else {
- return root;
- }
- }
- }
- interface Stack<E> {
- // Elementi na stekot se objekti od proizvolen tip.
- // Metodi za pristap:
- public boolean isEmpty();
- // Vrakja true ako i samo ako stekot e prazen.
- public E peek();
- // Go vrakja elementot na vrvot od stekot.
- // Metodi za transformacija:
- public void clear();
- // Go prazni stekot.
- public void push(E x);
- // Go dodava x na vrvot na stekot.
- public E pop();
- // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
- }
- class ArrayStack<E> implements Stack<E> {
- private E[] elems;
- private int depth;
- @SuppressWarnings("unchecked")
- public ArrayStack(int maxDepth) {
- // Konstrukcija na nov, prazen stek.
- elems = (E[]) new Object[maxDepth];
- depth = 0;
- }
- public boolean isEmpty() {
- // Vrakja true ako i samo ako stekot e prazen.
- return (depth == 0);
- }
- public E peek() {
- // Go vrakja elementot na vrvot od stekot.
- if (depth == 0)
- throw new NoSuchElementException();
- return elems[depth - 1];
- }
- public void clear() {
- // Go prazni stekot.
- for (int i = 0; i < depth; i++)
- elems[i] = null;
- depth = 0;
- }
- public void push(E x) {
- // Go dodava x na vrvot na stekot.
- elems[depth++] = x;
- }
- public E pop() {
- // Go otstranuva i vrakja elementot shto e na vrvot na stekot.
- if (depth == 0)
- throw new NoSuchElementException();
- E topmost = elems[--depth];
- elems[depth] = null;
- return topmost;
- }
- }
- public class NodeDistance {
- public static void main(String[] args) throws Exception {
- int i, j, k;
- int index;
- String action;
- String line;
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st;
- int N = Integer.parseInt(br.readLine());
- BNode<String> nodes[] = new BNode[N];
- BTree<String> tree = new BTree<String>();
- for (i = 0; i < N; i++)
- nodes[i] = new BNode<String>();
- for (i = 0; i < N; i++) {
- line = br.readLine();
- st = new StringTokenizer(line);
- index = Integer.parseInt(st.nextToken());
- nodes[index].info = st.nextToken();
- action = st.nextToken();
- if (action.equals("LEFT")) {
- tree.addChildNode(nodes[Integer.parseInt(st.nextToken())],
- BNode.LEFT, nodes[index]);
- } else if (action.equals("RIGHT")) {
- tree.addChildNode(nodes[Integer.parseInt(st.nextToken())],
- BNode.RIGHT, nodes[index]);
- } else {
- // this node is the root
- tree.makeRootNode(nodes[index]);
- }
- }
- int cases = Integer.parseInt(br.readLine());
- for (int l = 0; l < cases; l++) {
- String split[] = br.readLine().split(" ");
- String from = split[0];
- String to = split[1];
- BNode<String> fromNode = tree.getNode(from);
- BNode<String> toNode = tree.getNode(to);
- if (fromNode == null || toNode == null) {
- System.out.println("ERROR");
- continue;
- }
- int x = tree.isUnder(fromNode, toNode);
- int y = tree.isUnder(toNode, fromNode);
- System.out.println(x + " " + y);
- }
- br.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement