SHARE
TWEET

Untitled

a guest Jan 22nd, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2. import java.lang.StringBuilder;
  3.  
  4. class CollectionException extends Exception {
  5.     public CollectionException(String msg) {
  6.         super(msg);
  7.     }
  8. }
  9.  
  10. interface Collection {
  11.     static final String ERR_MSG_EMPTY = "Collection is empty.";
  12.     static final String ERR_MSG_FULL = "Collection is full.";
  13.     boolean isEmpty();
  14.     boolean isFull();
  15.     int count();
  16.     String toStg();
  17. }
  18.  
  19. class Deque<T> implements Collection {
  20.  
  21.     private static final int DEFAULT_CAPACITY = 256;
  22.  
  23.     @SuppressWarnings("unchecked")
  24.     T[] items = (T[]) new Object[DEFAULT_CAPACITY];
  25.     int front;
  26.     int back;
  27.     int count;
  28.  
  29.     @SuppressWarnings("unchecked")
  30.     public Deque() {
  31.         T[] items = (T[]) new Object[DEFAULT_CAPACITY];
  32.         int front = 0;
  33.         int back = 0;
  34.         int count = 0;
  35.     }
  36.  
  37.     public int count() {
  38.         return count;
  39.     }
  40.  
  41.     public boolean isEmpty() {
  42.         return count == 0;
  43.     }
  44.  
  45.     public boolean isFull() {
  46.         return count == items.length;
  47.     }
  48.  
  49.     public String toStg() {
  50.         StringBuilder sb = new StringBuilder("[");
  51.         if (count > 0) {
  52.             sb.append(items[front]);
  53.             for (int i = 1; i < count; i++) {
  54.                 sb.append(", ");
  55.                 sb.append(items[(front + i) % items.length]);
  56.             }
  57.         }
  58.         sb.append("]");
  59.         return sb.toString();
  60.     }
  61.  
  62.     public T front() throws CollectionException {
  63.         if (isEmpty())
  64.             throw new CollectionException(ERR_MSG_EMPTY);
  65.         return items[front];
  66.     }
  67.  
  68.     public T back() throws CollectionException {
  69.         if (isEmpty())
  70.             throw new CollectionException(ERR_MSG_EMPTY);
  71.         return items[(back - 1 + items.length) % items.length];
  72.     }
  73.  
  74.     public void enqueue(T x) throws CollectionException {
  75.         if (isFull())
  76.             throw new CollectionException(ERR_MSG_FULL);
  77.         items[back] = x;
  78.         back = (back + 1) % items.length;
  79.         count++;
  80.     }
  81.  
  82.     public void enqueueFront(T x) throws CollectionException {
  83.         if (isFull())
  84.             throw new CollectionException(ERR_MSG_FULL);
  85.         front = (front - 1 + items.length) % items.length;
  86.         items[front] = x;
  87.         count++;
  88.     }
  89.  
  90.     public T dequeue() throws CollectionException {
  91.         if (isEmpty())
  92.             throw new CollectionException(ERR_MSG_EMPTY);
  93.         T temp = items[front];
  94.         items[front] = null;
  95.         front = (front + 1) % items.length;
  96.         count--;
  97.         return temp;
  98.     }
  99.  
  100.     public T dequeueBack() throws CollectionException {
  101.         if (isEmpty())
  102.             throw new CollectionException(ERR_MSG_EMPTY);
  103.         T temp = items[(back - 1 + items.length) % items.length];
  104.         items[(back - 1 + items.length) % items.length] = null;
  105.         back = (back - 1 + items.length) % items.length;
  106.         count--;
  107.         return temp;
  108.     }
  109.  
  110. }
  111.  
  112. class Edge {
  113.  
  114.     int v1;
  115.     int v2;
  116.  
  117.     public Edge(int v1, int v2) {
  118.         this.v1 = v1;
  119.         this.v2 = v2;
  120.     }
  121.  
  122. }
  123.  
  124. class Graph {
  125.  
  126.     public String type;
  127.     public int numVerts;
  128.     public Edge[] edges;
  129.  
  130.     private String entry;
  131.     private String exit;
  132.     private String order;
  133.     private int[] paths;
  134.  
  135.     public Graph(String type, int numVerts, Edge[] edges) {
  136.         this.type = type;
  137.         this.numVerts = numVerts;
  138.         this.edges = edges;
  139.     }
  140.  
  141.     public void walks(int length) {
  142.         int[][] nMatrix = new int[numVerts][numVerts];
  143.         for (int i = 0; i < edges.length; i++) {
  144.             nMatrix[edges[i].v1][edges[i].v2] = 1;
  145.             if (type.equals("undirected"))
  146.                 nMatrix[edges[i].v2][edges[i].v1] = 1;
  147.         }
  148.         int[][] walks = nMatrix;
  149.         for (int i = 1; i < length; i++) {
  150.             walks = multiplyMatrices(walks, nMatrix);
  151.         }
  152.         for (int i = 0; i < numVerts; i++) {
  153.             for (int j = 0; j < numVerts; j++) {
  154.                 System.out.print(walks[i][j] + " ");   
  155.             }
  156.             System.out.println();
  157.         }
  158.     }
  159.  
  160.    
  161.  
  162.     public void dfsFull() {
  163.         boolean[] visited = new boolean[numVerts];
  164.         entry = "";
  165.         exit = "";
  166.         for (int i = 0; i < numVerts; i++) {
  167.             if (!visited[i])
  168.                 dfs(i, visited);
  169.         }
  170.         System.out.println(entry);
  171.         System.out.println(exit);
  172.     }
  173.  
  174.     private void dfs(int v, boolean[] visited) {
  175.         entry += Integer.toString(v) + " ";
  176.         visited[v] = true;
  177.         int[] neighbors = getNeighbors(v);
  178.         for (int i = 0; i < neighbors.length; i++) {
  179.             if (!visited[neighbors[i]])
  180.                 dfs(neighbors[i], visited);
  181.         }
  182.         exit += Integer.toString(v) + " ";
  183.     }
  184.  
  185.     public void bfsFull() throws Exception {
  186.         boolean[] visited = new boolean[numVerts];
  187.         order = "";
  188.         for (int i = 0; i < numVerts; i++) {
  189.             if (!visited[i])
  190.                 bfs(i, visited, "bfs");
  191.         }
  192.         System.out.println(order);
  193.     }
  194.  
  195.     private void bfs(int v, boolean[] visited, String mode) throws Exception {
  196.         Deque<Integer> q = new Deque<Integer>();
  197.         if (mode.equals("sp"))
  198.             paths[v] = 0;
  199.         visited[v] = true;
  200.         q.enqueue(v);
  201.         while (!q.isEmpty()) {
  202.             v = q.dequeue();
  203.             if (mode.equals("bfs"))
  204.                 order += v + " ";
  205.             int[] neighbors = getNeighbors(v);
  206.             for (int i = 0; i < neighbors.length; i++) {
  207.                 if (!visited[neighbors[i]]) {
  208.                     if (mode.equals("sp"))
  209.                         paths[neighbors[i]] = paths[v] + 1;
  210.                     visited[neighbors[i]] = true;
  211.                     q.enqueue(neighbors[i]);
  212.                 }
  213.             }
  214.         }
  215.     }
  216.  
  217.     public void sp(int v) throws Exception {
  218.         boolean[] visited = new boolean[numVerts];
  219.         order = "";
  220.         paths = new int[numVerts];
  221.         for (int i = 0; i < numVerts; i++) {
  222.             paths[i] = -1;
  223.         }
  224.         bfs(v, visited, "sp");
  225.         for (int i = 0; i < numVerts; i++) {
  226.             System.out.println(i + " " + paths[i]);
  227.         }
  228.     }
  229.  
  230.     private int[][] multiplyMatrices(int[][] m1, int[][] m2) {
  231.         int[][] multipliedMatrix = new int[m1.length][m1.length];
  232.         int sum = 0;
  233.         for (int i1 = 0; i1 < m1.length; i1++) {
  234.             for (int i2 = 0; i2 < m2[0].length; i2++) {
  235.                 for (int j = 0; j < m1[0].length; j++) {
  236.                     sum += m1[i1][j] * m2[j][i2];
  237.                 }
  238.                 multipliedMatrix[i1][i2] = sum;
  239.                 sum = 0;
  240.             }
  241.         };
  242.         return multipliedMatrix;
  243.     }
  244.  
  245.     private int countOccurences(int element) {
  246.         int counter = 0;
  247.         for (int i = 0; i < edges.length; i++) {
  248.             if (type.equals("directed")) {
  249.                 if (edges[i].v1 == element)
  250.                     counter++;
  251.             } else {
  252.                 if (edges[i].v1 == element || edges[i].v2 == element) {
  253.                     counter++;
  254.                 }
  255.             }
  256.         }
  257.         return counter;
  258.     }
  259.  
  260.     private int[] getNeighbors(int v) {
  261.         int[] neighbors = new int[countOccurences(v)];
  262.         int index = 0;
  263.         for (int i = 0; i < edges.length; i++) {
  264.             if (edges[i].v1 == v) {
  265.                 neighbors[index] = edges[i].v2;
  266.                 index++;
  267.             }
  268.             if (type.equals("undirected")) {
  269.                 if (edges[i].v2 == v) {
  270.                     neighbors[index] = edges[i].v1;
  271.                     index++;
  272.                 }
  273.             }
  274.         }
  275.         insertionSort(neighbors);
  276.         return neighbors;
  277.     }
  278.  
  279.     private void insertionSort(int[] array) {
  280.         int temp;
  281.         for (int i = 1; i < array.length; i++) {
  282.             temp = array[i];
  283.             for (int j = i; j > 0; j--) {
  284.                 if (array[j - 1] > temp) {
  285.                     array[j] = array[j - 1];
  286.                     array[j - 1] = temp;
  287.                 } else {
  288.                     array[j] = temp;
  289.                     break; 
  290.                 }
  291.             }
  292.         }
  293.     }
  294.  
  295. }
  296.  
  297. public class Naloga3 {
  298.  
  299.     public static void main(String[] args) throws Exception {
  300.         String graphType = args[0];
  301.         Scanner sc = new Scanner(System.in);
  302.         int numVerts = Integer.parseInt(sc.nextLine().trim());
  303.         StringBuilder sb1 = new StringBuilder();
  304.         StringBuilder sb2 = new StringBuilder();
  305.         while (sc.hasNextLine()) {
  306.             String[] line = sc.nextLine().trim().split(" ");
  307.             sb1.append(line[0] + ":");
  308.             sb2.append(line[1] + ":");
  309.         }
  310.         String[] v1 = sb1.toString().split(":");
  311.         String[] v2 = sb2.toString().split(":");
  312.         Edge[] edges = new Edge[v1.length];
  313.         for (int i = 0; i < v1.length; i++) {
  314.             edges[i] = new Edge(Integer.parseInt(v1[i]), Integer.parseInt(v2[i]));
  315.         }
  316.         Graph g = new Graph(graphType, numVerts, edges);
  317.         switch (args[1]) {
  318.             case "walks":   g.walks(Integer.parseInt(args[2]));
  319.                             break;
  320.             case "dfs":     g.dfsFull();
  321.                             break;
  322.             case "bfs":     g.bfsFull();
  323.                             break;
  324.             case "sp":      g.sp(Integer.parseInt(args[2]));
  325.                             break;
  326.         }
  327.     }
  328.  
  329. }
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