Guest User

OvelappingPath.java

a guest
Jan 27th, 2019
178
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedWriter;
  2. import java.io.IOException;
  3. import java.io.InputStream;
  4. import java.io.PrintWriter;
  5. import java.util.ArrayList;
  6. import java.util.InputMismatchException;
  7. import java.io.IOException;
  8. import java.io.OutputStreamWriter;
  9. import java.io.OutputStream;
  10. import java.io.Writer;
  11. import java.util.LinkedList;
  12.  
  13. class OverlappingPathSolution {
  14.     static InputReader in = new InputReader(System.in);
  15.     static OutputWriter out = new OutputWriter(System.out);
  16.     static ArrayList<Integer> path;
  17.     static class Graph {
  18.         int V;
  19.         LinkedList<Integer>[] adjListArray;
  20.         Graph(int V) {
  21.             this.V = V;
  22.             adjListArray = new LinkedList[V];
  23.             for(int i = 0; i < V ; i++){
  24.                 adjListArray[i] = new LinkedList<Integer>();
  25.             }
  26.         }
  27.     }
  28.  
  29.     static void addEdge(Graph graph, int src, int dest) {
  30.         graph.adjListArray[src].add(dest);
  31.         graph.adjListArray[dest].add(src);
  32.     }
  33.  
  34.     static void depthFirstSearch(Graph graph, int source, int dest, boolean[] visited) {
  35.         visited[source] = true;
  36.         path.add(source);
  37.         if(source == dest) return;
  38.         for(int i = 0; i < graph.adjListArray[source].size(); ++i) {
  39.             if(!visited[graph.adjListArray[source].get(i)]) {
  40.                 depthFirstSearch(graph, graph.adjListArray[source].get(i), dest, visited);
  41.             }
  42.         }
  43.     }
  44.  
  45.     static void depthFirstSearch(Graph graph, int source, int dest) {
  46.         boolean[] visited = new boolean[graph.V];
  47.         path = new ArrayList<>();
  48.         depthFirstSearch(graph, source, dest, visited);
  49.     }
  50.     static void printGraph(Graph graph) {
  51.         for(int v = 1; v < graph.V; v++) {
  52.             out.printLine("Adjacency list of vertex "+ (v));
  53.             out.print("head : ");
  54.             for(Integer pCrawl: graph.adjListArray[v]){
  55.                 out.print(" -> "+(pCrawl));
  56.             }
  57.             out.printLine("\n");
  58.         }
  59.     }
  60.  
  61.     public static int findMaxGCD() {
  62.         // Computing highest element
  63.         int n = path.size();
  64.         int high = 0;
  65.         for (int i = 0; i < n; i++)
  66.             high = Math.max(high, path.get(i));
  67.  
  68.         // Array to store the count of divisors
  69.         // i.e. Potential GCDs
  70.         int divisors[] =new int[high + 1];
  71.  
  72.         // Iterating over every element
  73.         for (int i = 0; i < n; i++)
  74.         {
  75.             // Calculating all the divisors
  76.             for (int j = 1; j <= Math.sqrt(path.get(i)); j++)
  77.             {
  78.                 // Divisor found
  79.                 if (path.get(i) % j == 0)
  80.                 {
  81.                     // Incrementing count for divisor
  82.                     divisors[j]++;
  83.  
  84.                     // Element/divisor is also a divisor
  85.                     // Checking if both divisors are
  86.                     // not same
  87.                     if (j != path.get(i) / j)
  88.                         divisors[path.get(i) / j]++;
  89.                 }
  90.             }
  91.         }
  92.  
  93.         // Checking the highest potential GCD
  94.         for (int i = high; i >= 1; i--)
  95.  
  96.             // If this divisor can divide at least 2
  97.             // numbers, it is a GCD of at least 1 pair
  98.             if (divisors[i] > 1)
  99.                 return i;
  100.         return 1;
  101.     }
  102.     public static void main(String[] args) throws IOException {
  103.  
  104.         int t = in.readInt();
  105.         while (t-- > 0) {
  106.             int nodes = in.readInt();
  107.             Graph graph = new Graph(nodes + 1);
  108.             for (int i = 0; i < nodes - 1; ++i) {
  109.                 addEdge(graph, in.readInt(), in.readInt());
  110.             }
  111.             int u = in.readInt();
  112.             int v = in.readInt();
  113.             depthFirstSearch(graph, u, v);
  114.             out.printLine(path);
  115.             out.printLine(findMaxGCD());
  116.         }
  117.         out.flush();
  118.         out.close();
  119.  
  120.     }
  121.  
  122.     private static class InputReader {
  123.         private InputStream stream;
  124.         private byte[] buf = new byte[1024];
  125.         private int curChar;
  126.         private int numChars;
  127.         private SpaceCharFilter filter;
  128.  
  129.         public InputReader(InputStream stream) {
  130.             this.stream = stream;
  131.         }
  132.  
  133.         public int read() {
  134.             if (numChars == -1) {
  135.                 throw new InputMismatchException();
  136.             }
  137.             if (curChar >= numChars) {
  138.                 curChar = 0;
  139.                 try {
  140.                     numChars = stream.read(buf);
  141.                 } catch (IOException e) {
  142.                     throw new InputMismatchException();
  143.                 }
  144.                 if (numChars <= 0) {
  145.                     return -1;
  146.                 }
  147.             }
  148.             return buf[curChar++];
  149.         }
  150.  
  151.         public int readInt() {
  152.             int c = read();
  153.             while (isSpaceChar(c)) {
  154.                 c = read();
  155.             }
  156.             int sgn = 1;
  157.             if (c == '-') {
  158.                 sgn = -1;
  159.                 c = read();
  160.             }
  161.             int res = 0;
  162.             do {
  163.                 if (c < '0' || c > '9') {
  164.                     throw new InputMismatchException();
  165.                 }
  166.                 res *= 10;
  167.                 res += c - '0';
  168.                 c = read();
  169.             } while (!isSpaceChar(c));
  170.             return res * sgn;
  171.         }
  172.  
  173.         public String readString() {
  174.             int c = read();
  175.             while (isSpaceChar(c)) {
  176.                 c = read();
  177.             }
  178.             StringBuilder res = new StringBuilder();
  179.             do {
  180.                 res.appendCodePoint(c);
  181.                 c = read();
  182.             } while (!isSpaceChar(c));
  183.             return res.toString();
  184.         }
  185.  
  186.         public double readDouble() {
  187.             int c = read();
  188.             while (isSpaceChar(c)) {
  189.                 c = read();
  190.             }
  191.             int sgn = 1;
  192.             if (c == '-') {
  193.                 sgn = -1;
  194.                 c = read();
  195.             }
  196.             double res = 0;
  197.             while (!isSpaceChar(c) && c != '.') {
  198.                 if (c == 'e' || c == 'E') {
  199.                     return res * Math.pow(10, readInt());
  200.                 }
  201.                 if (c < '0' || c > '9') {
  202.                     throw new InputMismatchException();
  203.                 }
  204.                 res *= 10;
  205.                 res += c - '0';
  206.                 c = read();
  207.             }
  208.             if (c == '.') {
  209.                 c = read();
  210.                 double m = 1;
  211.                 while (!isSpaceChar(c)) {
  212.                     if (c == 'e' || c == 'E') {
  213.                         return res * Math.pow(10, readInt());
  214.                     }
  215.                     if (c < '0' || c > '9') {
  216.                         throw new InputMismatchException();
  217.                     }
  218.                     m /= 10;
  219.                     res += (c - '0') * m;
  220.                     c = read();
  221.                 }
  222.             }
  223.             return res * sgn;
  224.         }
  225.  
  226.         public long readLong() {
  227.             int c = read();
  228.             while (isSpaceChar(c)) {
  229.                 c = read();
  230.             }
  231.             int sgn = 1;
  232.             if (c == '-') {
  233.                 sgn = -1;
  234.                 c = read();
  235.             }
  236.             long res = 0;
  237.             do {
  238.                 if (c < '0' || c > '9') {
  239.                     throw new InputMismatchException();
  240.                 }
  241.                 res *= 10;
  242.                 res += c - '0';
  243.                 c = read();
  244.             } while (!isSpaceChar(c));
  245.             return res * sgn;
  246.         }
  247.  
  248.         public boolean isSpaceChar(int c) {
  249.             if (filter != null) {
  250.                 return filter.isSpaceChar(c);
  251.             }
  252.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  253.         }
  254.  
  255.         public String next() {
  256.             return readString();
  257.         }
  258.  
  259.         public interface SpaceCharFilter {
  260.             public boolean isSpaceChar(int ch);
  261.         }
  262.     }
  263.  
  264.     private static class OutputWriter {
  265.         private final PrintWriter writer;
  266.  
  267.         public OutputWriter(OutputStream outputStream) {
  268.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  269.         }
  270.  
  271.         public OutputWriter(Writer writer) {
  272.             this.writer = new PrintWriter(writer);
  273.         }
  274.  
  275.         public void print(Object... objects) {
  276.             for (int i = 0; i < objects.length; i++) {
  277.                 if (i != 0) {
  278.                     writer.print(' ');
  279.                 }
  280.                 writer.print(objects[i]);
  281.             }
  282.             writer.flush();
  283.         }
  284.  
  285.         public void printLine(Object... objects) {
  286.             print(objects);
  287.             writer.println();
  288.             writer.flush();
  289.         }
  290.  
  291.         public void close() {
  292.             writer.close();
  293.         }
  294.  
  295.         public void flush() {
  296.             writer.flush();
  297.         }
  298.     }
  299.  
  300.     private static class IOUtils {
  301.  
  302.         public static int[] readIntArray(InputReader in, int size) {
  303.             int[] array = new int[size];
  304.             for (int i = 0; i < size; i++)
  305.                 array[i] = in.readInt();
  306.             return array;
  307.         }
  308.  
  309.     }
  310. }
RAW Paste Data