SHARE
TWEET

ads

a guest Mar 23rd, 2019 107 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. WEEK-4///////////////////////////////////////////////////////////////////////////////////////////////////////
  2. class ArrayStack {
  3.   private Object[] elements;
  4.   private int size;
  5.   private int capacity;
  6.  
  7.   /**
  8.    * Creates an empty ArrayStack with capacity 1.
  9.    */
  10.   public ArrayStack() {
  11.     elements  = new Object[1];
  12.     size = 0;
  13.     capacity = 1;
  14.   }
  15.  
  16.   /**
  17.    * @return The size of this ArrayStack.
  18.    */
  19.   public int size() {
  20.     return size;
  21.   }
  22.  
  23.   /**
  24.    * @return `true` iff this ArrayStack is empty, `false` otherwise.
  25.    */
  26.   public boolean isEmpty() {
  27.     return size == 0;
  28.   }
  29.  
  30.   /**
  31.    * @return `true` iff the size is equal to the capacity, `false` otherwise.
  32.    */
  33.   public boolean isFull() {
  34.     return size == capacity;
  35.   }
  36.  
  37.   /**
  38.    * @return the top element of the stack without removing it
  39.    */
  40.   public Object peek() throws EmptyStackException {
  41.     if(size == 0){
  42.       throw new EmptyStackException();
  43.     }
  44.     else{
  45.       return elements[size-1];
  46.     }
  47.   }
  48.  
  49.   /**
  50.    * Adds `o` to the stack.
  51.    * If capacity of stack was too small, capacity is doubled and `o` is added.
  52.    *
  53.    * @param o
  54.    *     the element to add to the stack.
  55.    */
  56.   public void push(Object o) {
  57.     if(size == capacity){
  58.       Object[] newArr = new Object[capacity*2];
  59.       for(int i=0; i<capacity; i++)
  60.         newArr[i] = elements[i];
  61.       elements = newArr;
  62.       capacity *= 2;
  63.     }
  64.  
  65.     elements[size++] = o;
  66.   }
  67.  
  68.   /**
  69.    * Removes the top element from the stack.
  70.    * If removing top would make the stack use less than 25% of its capacity,
  71.    * then the capacity is halved.
  72.    *
  73.    * @return the element which was at the top of the stack.
  74.    * @throws EmptyStackException
  75.    *     iff the queue is empty
  76.    */
  77.   public Object pop() throws EmptyStackException {
  78.     if(size == 0){
  79.       throw new EmptyStackException();
  80.     }
  81.    
  82.     Object obj = elements[--size];
  83.    
  84.     if((size < capacity/4) && (capacity/2 >= 1)){
  85.       Object[] eleArr = new Object[capacity/2];
  86.       for(int i = 0; i<size; i++)
  87.         eleArr[i] = elements[i];
  88.       elements = eleArr;
  89.       capacity /= 2;
  90.     }
  91.    
  92.     return obj;
  93.   }
  94.  
  95.   /**
  96.    * @return a String representation of the ArrayStack
  97.    * Example output for ArrayStack with 2 elements and capacity 5:
  98.    * <ArrayStack[1,2]>(Size=2, Cap=5)
  99.    */
  100.   public String toString() {
  101.     String str;
  102.     if(size == 0){
  103.       str = String.format("<ArrayStack[]>(Size=%d, Cap=%d)", size, capacity);
  104.     }
  105.     else{
  106.       str = String.format("<ArrayStack[%s", elements[0].toString());
  107.       for(int i=1; i<size; i++){
  108.         str += String.format(",%s", elements[i].toString());
  109.       }
  110.       str += String.format("]>(Size=%d, Cap=%d)", size, capacity);
  111.     }
  112.     return str;
  113.     }
  114.  
  115.   // For testing, do not remove or change.
  116.   public Object[] getElements() {
  117.     return elements;
  118.   }
  119. }
  120. //////////////////////////////////////////////////////////////////////////////////////////////////////////////
  121.  
  122. class Solution {
  123.   /**
  124.    * Computes whether the BinaryTree is complete.
  125.    *
  126.    * @param tree
  127.    *     the BinaryTree to check.
  128.    * @return true iff the BinaryTree is complete, else false.
  129.    */
  130.   public static boolean isTreeComplete(BinaryTree tree) {
  131.     return isTreeComplete(tree, 0, totalNodes(tree));
  132.   }
  133.  
  134.   private static int totalNodes(BinaryTree tree){
  135.     if(tree == null){
  136.       return 0;
  137.     }
  138.    
  139.     return 1 + totalNodes(tree.getLeft()) + totalNodes(tree.getRight());
  140.   }
  141.  
  142.   public static boolean isTreeComplete(BinaryTree tree, int index, int totalNodes){
  143.     if(tree == null){
  144.       return true;
  145.     }
  146.    
  147.     if(index >= totalNodes){
  148.       return false;
  149.     }
  150.    
  151.     return isTreeComplete(tree.getLeft(), 2*index+1, totalNodes) && isTreeComplete(tree.getRight(), 2*index+2, totalNodes);
  152.   }
  153.  
  154. }
  155. ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  156. import java.util.*;
  157.  
  158. /**
  159.  * Iterates lazily over a binary tree in a depth-first manner. For instance a tree
  160.  * with 8 as it's root and 4 and 10 as it's children should be iterated as: 8 ->
  161.  * 4 -> 10.
  162.  */
  163. class BinaryTreeIterator<V> implements Iterator<V> {
  164.   BTree<V> tree;
  165.   Stack<Position<V>> stack = new Stack<Position<V>>();
  166.   /**
  167.    * Constructor.
  168.    * Should reset on a new tree.
  169.    *
  170.    * @param tree
  171.    *     takes the tree
  172.    */
  173.   public BinaryTreeIterator(BTree<V> tree) {
  174.     this.tree = tree;
  175.     if(tree.getRoot() != null)
  176.       stack.push(tree.getRoot());
  177.   }
  178.  
  179.   /**
  180.    * @return True if there is a next element in the iterator, else False
  181.    */
  182.   @Override
  183.   public boolean hasNext() {
  184.     return !stack.isEmpty();
  185.   }
  186.  
  187.   /**
  188.    * Get the next element of the iterator and shift
  189.    * iterator by one.
  190.    *
  191.    * @return current element value
  192.    * @post iterator is moved to next element
  193.    */
  194.   @Override
  195.   public V next() {
  196.    
  197.     if(stack.isEmpty()) return null;
  198.    
  199.     Position<V> temp = stack.pop();
  200.     try{
  201.       if(tree.hasRight(temp)){
  202.         stack.push(tree.getRight(temp));  
  203.       }
  204.       if(tree.hasLeft(temp)){
  205.         stack.push(tree.getLeft(temp));
  206.       }
  207.     }
  208.     catch(InvalidPositionException e){
  209.       //hmm
  210.     }
  211.      
  212.     return temp.getValue();
  213.   }
  214.  
  215.   /**
  216.    * Skip a single element of the iterator.
  217.    *
  218.    * @post iterator is moved to next element.
  219.    */
  220.   @Override
  221.   public void remove() {
  222.     next();
  223.   }
  224. }
  225.  
  226. /**
  227.  * DO NOT MODIFY
  228.  */
  229. interface Position<V> {
  230.   /**
  231.    * @return the key of this position.
  232.    */
  233.   public int getKey();
  234.  
  235.   /**
  236.    * @return the value of the position.
  237.    */
  238.   public V getValue();
  239. }
  240.  
  241. interface BTree<V> {
  242.   /**
  243.    * @return the root of the tree
  244.    */
  245.   public Position<V> getRoot();
  246.  
  247.   /**
  248.    * Get the left child of a position.
  249.    *
  250.    * @param v
  251.    *     the position to get the child of.
  252.    * @return the child of the position iff hasLeft(v) is true.
  253.    * @throws InvalidPositionException
  254.    *     else
  255.    */
  256.   public Position<V> getLeft(Position<V> v) throws InvalidPositionException;
  257.  
  258.   /**
  259.    * Get the right child of a position.
  260.    *
  261.    * @param v
  262.    *     the position to get the child of.
  263.    * @return the child of the position iff hasRight(v) is true.
  264.    * @throws InvalidPositionException
  265.    *     else
  266.    */
  267.   public Position<V> getRight(Position<V> v) throws InvalidPositionException;
  268.  
  269.   /**
  270.    * Check if a position has a left child.
  271.    *
  272.    * @param v
  273.    *     position to check.
  274.    * @return true iff v has a left child.
  275.    * @throws InvalidPositionException
  276.    *     if v is not valid (e.g. null)
  277.    */
  278.   public boolean hasLeft(Position<V> v) throws InvalidPositionException;
  279.  
  280.   /**
  281.    * Check if a position has a right child.
  282.    *
  283.    * @param v
  284.    *     position to check.
  285.    * @return true iff v has a right child.
  286.    * @throws InvalidPositionException
  287.    *     if v is not valid (e.g. null)
  288.    */
  289.   public boolean hasRight(Position<V> v) throws InvalidPositionException;
  290.  
  291.   /**
  292.    * Adds a new entry to the tree.
  293.    *
  294.    * @param key
  295.    *     to use.
  296.    * @param value
  297.    *     to add.
  298.    */
  299.   public void add(int key, V value);
  300. }
  301. /////////////////////////////////////////////////////////////////////////////////////////////////////////
  302. WEEK-5
  303.  
  304. class Solution {
  305.   /**
  306.    * @param elements
  307.    *     Array of integers to be sorted.
  308.    */
  309.   public static void selectionSort(int[] elements) {
  310.     for(int i=0; i<elements.length-1; i++){
  311.       int min = i;
  312.       for(int j=i+1; j<elements.length; j++){
  313.         if(elements[min]>elements[j])
  314.           min = j;
  315.       }
  316.       int swap = elements[i];
  317.       elements[i] = elements[min];
  318.       elements[min] = swap;
  319.     }
  320.   }
  321. }
  322. //////////////////////////////////////////////////////////////////////////////////////////////////
  323. class Solution {
  324.   /**
  325.    * @param elements
  326.    *     Array of integers to be sorted.
  327.    */
  328.   public static void quickSort(int[] elements) {
  329.     quickSort(elements, 0, elements.length-1);
  330.   }
  331.  
  332.   public static void quickSort(int [] elements, int l, int r)
  333.   {
  334.     if(l>=r)
  335.     return;
  336.    
  337.     int left=l;
  338.     int right=r-1;
  339.     int pivot=r;
  340.    
  341.     while(left<=right)
  342.     {
  343.       while(left<=right && elements[left]<=elements[pivot])
  344.       left++;
  345.      
  346.       while(left<=right && elements[right]>=elements[pivot])
  347.       right--;
  348.      
  349.       if(left<= right){
  350.         int temp=elements[left];
  351.         elements[left]=elements[right];
  352.         elements[right]=temp;
  353.         left++;
  354.         right--;
  355.       }
  356.     }
  357.      int temp=elements[left];
  358.       elements[left]=elements[pivot];
  359.       elements[pivot]=temp;
  360.      
  361.       quickSort(elements, l, left-1);
  362.       quickSort(elements, left+1, r);
  363.  
  364.   }
  365. }
  366. ///////////////////////////////////////////////////////////////////////////////////////////
  367.  
  368. WEEK-6
  369.  
  370. import java.util.*;
  371.  
  372. class Solution {
  373.   @SuppressWarnings("unchecked")
  374.   public static Queue<Integer>[] fillBuckets(int[] array) {
  375.     if(array == null) return null;
  376.     if(array.length == 0) return new LinkedList[0];
  377.    
  378.     int vmin = array[0];
  379.     int vmax = array[0];
  380.     if(array.length > 1){
  381.       for(int i=1; i<array.length; i++){
  382.         if(array[i] < vmin)
  383.           vmin = array[i];
  384.         else if(array[i] > vmax)
  385.           vmax = array[i];
  386.       }
  387.     }
  388.    
  389.     Queue<Integer>[] buckets = new LinkedList[vmax - vmin + 1];
  390.    
  391.     for(int i=0; i<array.length; i++){
  392.       if(buckets[array[i]-vmin] == null){
  393.         buckets[array[i]-vmin] = new LinkedList<Integer>();
  394.       }
  395.       buckets[array[i]-vmin].add(array[i]);
  396.     }
  397.     return buckets;
  398.   }
  399.  
  400.   public static int[] readBuckets(Queue<Integer>[] buckets) {
  401.     if(buckets == null) return null;
  402.    
  403.     int[] array = new int[buckets.length];
  404.     int k=0;
  405.    
  406.     for(int i=0; i<buckets.length; i++){
  407.       while(buckets[i] != null && buckets[i].size()>0){
  408.         array[k++]=buckets[i].remove();
  409.       }
  410.     }
  411.    
  412.     int[] sorted_array = new int[k];
  413.     for(int i=0; i<k; i++){
  414.       sorted_array[i] = array[i];
  415.     }
  416.    
  417.     return sorted_array;
  418.   }
  419. }
  420. ///////////////////////////////////////////////////////////////////////////////////////////////////////
  421. class Solution {
  422.   public static void stableSort(String[][] table, int column) {
  423.     if(table==null) return;
  424.    
  425.     int len = table.length;
  426.     for(int i=1; i<len; i++){
  427.       String key = table[i][column];
  428.       String[] key_row = table[i];
  429.      
  430.       int j=i-1;
  431.       while(j>=0 && table[j][column].compareTo(key)>0){
  432.         table[j+1] = table[j];
  433.         j--;
  434.       }
  435.       table[j+1] = key_row;
  436.     }
  437.   }
  438. }
  439. ////////////////////////////////////////////////////////////////////////////////////////////////////
  440. WEEK-7
  441.  
  442. import java.util.*;
  443.  
  444. class MySet extends HashSet<String> {
  445.   private static final long serialVersionUID = 1L;
  446.  
  447.   public MySet() {
  448.     super();
  449.   }
  450.  
  451.   /**
  452.    * @return the union of the elements of this and that
  453.    */
  454.   public MySet union(MySet that) {
  455.     MySet result = new MySet();
  456.     Iterator<String> this_set = this.iterator();
  457.     while(this_set.hasNext()){
  458.       result.add(this_set.next());
  459.     }
  460.    
  461.     if(that != null){
  462.       Iterator<String> that_set = that.iterator();
  463.       while(that_set.hasNext()){
  464.         String elem = that_set.next();
  465.         if(!result.contains(elem)){
  466.           result.add(elem);
  467.         }
  468.       }
  469.     }
  470.     return result;
  471.   }
  472.  
  473.   /**
  474.    * @return the intersection of the elements of this and that
  475.    */
  476.   public MySet intersection(MySet that) {
  477.     MySet result = new MySet();
  478.    
  479.     if(that != null){
  480.       Iterator<String> that_set = that.iterator();
  481.       while(that_set.hasNext()){
  482.         String elem = that_set.next();
  483.         if(this.contains(elem)){
  484.           result.add(elem);
  485.         }
  486.       }
  487.     }
  488.     return result;
  489.   }
  490.  
  491.   /**
  492.    * @return the difference of the elements of this and that
  493.    */
  494.   public MySet difference(MySet that) {
  495.     MySet result = new MySet();
  496.     Iterator<String> this_set = this.iterator();
  497.     while(this_set.hasNext()){
  498.       result.add(this_set.next());
  499.     }
  500.    
  501.     if(that != null){
  502.       Iterator<String> that_set = that.iterator();
  503.       while(that_set.hasNext()){
  504.         String elem = that_set.next();
  505.         if(result.contains(elem)){
  506.           result.remove(elem);
  507.         }
  508.       }
  509.     }
  510.     return result;
  511.   }
  512.  
  513.   /**
  514.    * @return the exclusive or (XOR) of the elements of this and that
  515.    */
  516.   public MySet exclusiveOr(MySet that) {
  517.     MySet result = new MySet();
  518.     Iterator<String> this_set = this.iterator();
  519.     while(this_set.hasNext()){
  520.       result.add(this_set.next());
  521.     }
  522.    
  523.     if(that != null){
  524.       Iterator<String> that_set = that.iterator();
  525.       while(that_set.hasNext()){
  526.         String elem = that_set.next();
  527.         if(result.contains(elem)){
  528.           result.remove(elem);
  529.         }
  530.         else{
  531.           result.add(elem);
  532.         }
  533.       }
  534.     }
  535.     return result;
  536.   }
  537.  
  538.   /**
  539.    * @return a String representation of a MySet object
  540.    */
  541.   public String toString() {
  542.     String str = "<MySet{";
  543.     Iterator<String> this_set = this.iterator();
  544.     while(this_set.hasNext()){
  545.       str += this_set.next();
  546.     }
  547.     str += "}>";
  548.    
  549.     return str;
  550.   }
  551. }
  552. //////////////////////////////////////////////////////////////////////////////////////////////
  553. import java.util.*;
  554.  
  555. /**
  556.  * Entry objects are used to represent "Key-Value" pairs.
  557.  * An entry can be created by using new Entry(String key, Integer Value)
  558.  * The .equals() method of Entry will compare the keys only.
  559.  */
  560. class Entry {
  561.   public final String key;
  562.   public final Integer value;
  563.  
  564.   public Entry(String s, Integer v) {
  565.     key = s;
  566.     value = v;
  567.   }
  568.  
  569.   public boolean equals(String s) {
  570.     return s == null && key == null || key.equals(s);
  571.   }
  572.  
  573.   @Override
  574.   public boolean equals(Object o) {
  575.     return this == o || o != null && getClass() == o.getClass() && this.equals(((Entry) o).key);
  576.   }
  577.  
  578.   public String getKey() {
  579.     return key;
  580.   }
  581.  
  582.   public int getValue() {
  583.     return value;
  584.   }
  585. }
  586.  
  587. abstract class HashTable {
  588.   protected LinkedList<Entry>[] myTable;
  589.  
  590.   /**
  591.    * Constructs a new HashTable.
  592.    *
  593.    * @param capacity
  594.    *     to be used as capacity of the table.
  595.    * @throws IllegalArgumentException
  596.    *     if the input capacity is invalid.
  597.    */
  598.   @SuppressWarnings("unchecked")
  599.   public HashTable(int capacity) {
  600.     if(capacity <= 0)
  601.       throw new IllegalArgumentException();
  602.    
  603.     myTable = new LinkedList[capacity];
  604.   }
  605.  
  606.   /**
  607.    * Add a key value pair to the HashTable.
  608.    *
  609.    * @param key
  610.    *     to identify the value.
  611.    * @param value
  612.    *     that is identified by the key.
  613.    */
  614.   public void put(String key, Integer value) {
  615.     if(myTable == null) return;
  616.    
  617.     int hash = hash(key);
  618.     if(myTable[hash] == null){
  619.       myTable[hash] = new LinkedList<Entry>();
  620.     }
  621.    
  622.     if(containsKey(key)){
  623.       for(int i=0; i<myTable[hash].size(); i++){
  624.         Entry entry = myTable[hash].get(i);
  625.         if(entry.equals(key)){
  626.           myTable[hash].set(i, new Entry(key, value));
  627.           break;
  628.         }
  629.       }
  630.     }
  631.     else{
  632.       myTable[hash].add(new Entry(key, value));
  633.     }
  634.   }
  635.  
  636.   /**
  637.    * @param key
  638.    *     to look for in the HashTable.
  639.    * @return true iff the key is in the HashTable.
  640.    */
  641.   public boolean containsKey(String key) {
  642.     if(myTable == null) return false;
  643.    
  644.     int hash = hash(key);
  645.    
  646.     if(myTable[hash] != null){
  647.       for(Entry entry : myTable[hash]){
  648.         if(entry.equals(key)){
  649.           return true;
  650.         }
  651.       }
  652.     }
  653.     return false;
  654.   }
  655.  
  656.   /**
  657.    * Get a value from the HashTable.
  658.    *
  659.    * @param key
  660.    *     that identifies the value.
  661.    * @return the value associated with the key or `null` if the key is not in the HashTable.
  662.    */
  663.   public Integer get(String key) {
  664.     if(containsKey(key)){
  665.       int hash = hash(key);
  666.       for(Entry entry: myTable[hash]){
  667.         if(entry.equals(key)){
  668.           return entry.getValue();
  669.         }
  670.       }
  671.     }
  672.     return null;
  673.   }
  674.  
  675.   /**
  676.    * @return the capacity of the HashTable.
  677.    */
  678.   public int getCapacity() {
  679.     return myTable.length;
  680.   }
  681.  
  682.   /**
  683.    * Hashes a string/key.
  684.    *
  685.    * @param item
  686.    *     to hash.
  687.    * @return the hashcode of the string, modulo the capacity of the HashTable.
  688.    */
  689.   public abstract int hash(String item);
  690. }
  691. //////////////////////////////////////////////////////////////////////////////////////////////////
  692.  
  693. class ETHHash extends HashTable {
  694.   public ETHHash(int size) {
  695.     super(size);
  696.   }
  697.  
  698.   @Override
  699.   public int hash(String item) {
  700.     if(item == null)  return 0;
  701.    
  702.     int b = 1;
  703.    
  704.     for(int i=1; i <= item.length(); i++){
  705.       char currentChar = item.charAt(i-1);
  706.      
  707.       int bi = currentChar * ((b % 257) + 1);
  708.       b = bi;
  709.     }
  710.    
  711.     return b % getCapacity();
  712.   }
  713. }
  714.  
  715. class GNUCPPHash extends HashTable {
  716.   public GNUCPPHash(int size) {
  717.     super(size);
  718.   }
  719.  
  720.   @Override
  721.   public int hash(String item) {
  722.     if(item == null) return 0;
  723.    
  724.     int b = 0;
  725.    
  726.     for(int i=1; i <= item.length(); i++){
  727.       int c = item.charAt(i-1);
  728.      
  729.       int bi = 4 * b + c;
  730.       b = bi;
  731.     }
  732.    
  733.     return ( ((1 << 31)-1) & b ) % getCapacity();
  734.   }
  735. }
  736.  
  737. class GNUCC1Hash extends HashTable {
  738.   public GNUCC1Hash(int size) {
  739.     super(size);
  740.   }
  741.  
  742.   @Override
  743.   public int hash(String item) {
  744.     if(item == null)  return 0;
  745.    
  746.     int b = item.length();
  747.  
  748.     for(int i=1; i <= item.length(); i++){
  749.       char c = item.charAt(i-1);
  750.      
  751.       int bi = 613 * b + c;
  752.       b = bi;
  753.     }
  754.    
  755.     return ((1 << 31)-1 & b) % getCapacity();
  756.   }
  757. }
  758.  
  759. class HashCodeHash extends HashTable {
  760.   public HashCodeHash(int size) {
  761.     super(size);
  762.   }
  763.  
  764.   @Override
  765.   public int hash(String item) {
  766.     if (item == null) return 0;
  767.    
  768.     return Math.abs(item.hashCode()) % getCapacity();
  769.   }
  770. }
  771. ///////////////////////////////////////////////////////////////////////////////////////////////////
  772. WEEK-8
  773.  
  774. import java.util.*;
  775.  
  776. /**
  777.  * Implements a Depth first traversal of the Graph, starting at contructor vertex v. It
  778.  * should return nodes at most once. If there is a choice between multiple next nodes,
  779.  * always pick the lowest id node.
  780.  */
  781. class GraphIterator implements Iterator<Vertex> {
  782.   private Graph g;
  783.   private Vertex v;
  784.   private Stack<Vertex> stack;
  785.   private Set<Vertex> colored;
  786.   private int graphSize;
  787.  
  788.   public GraphIterator(Graph g, Vertex v) {
  789.     this.graphSize = 0;
  790.     this.g = g;
  791.     this.v = v;
  792.   }
  793.  
  794.   @Override
  795.   public boolean hasNext() {
  796.     if(this.g == null || this.v == null)  return false;
  797.    
  798.     return this.g.getAllVertices().size() != this.graphSize;
  799.   }
  800.  
  801.   @Override
  802.   public Vertex next() {
  803.     this.stack = new Stack<Vertex>();
  804.     this.colored = new TreeSet<Vertex>();
  805.     this.stack.push(v);
  806.    
  807.     Vertex current = null;
  808.    
  809.     for(int i=0; i<=this.graphSize; i++){
  810.      
  811.       do{
  812.         current = this.stack.pop();
  813.       }while(this.colored.contains(current));
  814.      
  815.       List<Vertex> neighbours = this.g.getNeighbours(current);
  816.       Collections.sort(neighbours, (a,b) -> b.getId()-a.getId());
  817.      
  818.       for(Vertex v : neighbours){
  819.         if(!this.colored.contains(v))
  820.           this.stack.push(v);
  821.       }
  822.      
  823.       this.colored.add(current);
  824.     }
  825.     this.graphSize++;
  826.     return current;
  827.   }
  828. }
  829. /////////////////////////////////////////////////////////////////////////////////////////
  830. class Solution {
  831.   public static int numberOfConnectedComponents(Graph g) {
  832.    
  833.     Collection<Vertex> unexplored = g.getAllVertices();
  834.    
  835.     for(int count=0; ; count++){
  836.       Iterator<Vertex> un_iter = unexplored.iterator();
  837.      
  838.       if(!un_iter.hasNext())  return count;
  839.      
  840.       Vertex v = un_iter.next();
  841.       Iterator<Vertex> iter = new GraphIterator(g, v);
  842.       List<Vertex> explored = new ArrayList<>();
  843.      
  844.       while(iter.hasNext()){
  845.         explored.add(iter.next());
  846.       }
  847.      
  848.       unexplored.removeAll(explored);
  849.     }
  850.   }
  851. }
  852. /////////////////////////////////////////////////////////////////////////////////////////////////
  853. import java.util.*;
  854.  
  855. class Solution {
  856.   /**
  857.    * Find the shortest path between v and u in the graph g.
  858.    *
  859.    * @param g
  860.    *     graph to search in.
  861.    * @param v
  862.    *     node to start from.
  863.    * @param u
  864.    *     node to reach.
  865.    * @return the nodes you that form the shortest path, including v and u. An
  866.    * empty list iff there is no path between v and u.
  867.    */
  868.   public static List<Vertex> shortestPath(Graph g, Vertex v, Vertex u) {
  869.     LinkedList<Vertex> slowPath = new LinkedList<Vertex>();
  870.     Iterator<Vertex> iter = new GraphIterator(g,v);
  871.    
  872.     while(iter.hasNext()){
  873.       Vertex x = iter.next();
  874.      
  875.       slowPath.add(x);
  876.      
  877.       if(x == u){
  878.         break;
  879.       }
  880.     }
  881.    
  882.     if(slowPath.get(slowPath.size()-1) != u){
  883.       return new ArrayList<>();
  884.     }
  885.    
  886.     List<Vertex> fastRevPath = new ArrayList<>();
  887.     int i = slowPath.size() - 1;
  888.    
  889.     while(true){
  890.       Vertex c = slowPath.get(i);
  891.      
  892.       List<Vertex> connected = g.getNeighbours(c);
  893.      
  894.       fastRevPath.add(c);
  895.      
  896.       if(c == v){
  897.         Collections.reverse(fastRevPath);
  898.         return fastRevPath;
  899.       }
  900.      
  901.       int index=0;
  902.      
  903.       for(Vertex vertex : slowPath){
  904.         if(!fastRevPath.contains(vertex) && connected.contains(vertex)){
  905.           i = index;
  906.           break;
  907.         }
  908.        
  909.         index++;
  910.       }
  911.     }
  912.    
  913.   }
  914. }
  915. ///////////////////////////////////////////////////////////////////////////////////
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