fensa08

[APS] Kolokvium 2 - Dedo Mraz na Raspust

Jan 21st, 2020
149
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Дедо Мраз на распуст Problem 9 (0 / 0)
  2.  
  3. Во земјата Лапонија живее Дедо Мраз. Во слободното време кога не е Нова Година, додека џуџињата си работат на играчките за следната година, Дедо Мраз има хоби. Тој сака да одгледува рибички. Но тој своите рибички ги одгледува во природни езера. Езерата се меѓусебно поврзани со рекички, и рекичките течат од едно езерце до друго. Рибите од едно езеро слободно можат преку рекичките да отидат во друго езеро. Секоја пролет дедо мраз сака да прави порибување на езерцата со нови рибички. Ваша задача е да му кажете на Дедо Мраз доколку тој пушти нови рибички во езерцето X, во колку други езерца ќе можат рибичките сами да стигнат, а со тоа да нема потреба тој самиот да ги порибува тие езерца.
  4.  
  5. Влез: Во првата линија од влезот е даден број N < 15 бројот на езерца. Во втората линија е даден број U < 20 бројот на реки меѓу езерцата. Во следните U линии се дадени парови од 2 броја R и Q, што значи постои рекичка која тече од R до Q, каде R и Q се броеви на езерцата. Во последната линија е даден број L, во кое езерце Дедо Мраз ќе ги пушти рибичките.
  6.  
  7. Излез: Во првата линија се испишува бројот, колку езерца освен почетното ќе бидат порибени. Во втората линија се испишува "Srekna Nova Godina".
  8.  
  9. Име на класата (Java): DedoMrazIRibite.
  10. ========================================================================================================================================
  11.  
  12. import java.util.Arrays;
  13. import java.util.NoSuchElementException;
  14. import java.util.Scanner;
  15.  
  16. class SLLNode<E> {
  17.     protected E element;
  18.     protected SLLNode<E> succ;
  19.  
  20.     public SLLNode(E elem, SLLNode<E> succ) {
  21.         this.element = elem;
  22.         this.succ = succ;
  23.     }
  24.  
  25.     @Override
  26.     public String toString() {
  27.         return element.toString();
  28.     }
  29. }
  30.  
  31. // Implementacija na redica
  32.  
  33. interface Queue<E> {
  34.  
  35.     // Elementi na redicata se objekti od proizvolen tip.
  36.  
  37.     // Metodi za pristap:
  38.  
  39.     public boolean isEmpty();
  40.  
  41.     // Vrakja true ako i samo ako redicata e prazena.
  42.  
  43.     public int size();
  44.  
  45.     // Ja vrakja dolzinata na redicata.
  46.  
  47.     public E peek();
  48.  
  49.     // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
  50.  
  51.     // Metodi za transformacija:
  52.  
  53.     public void clear();
  54.  
  55.     // Ja prazni redicata.
  56.  
  57.     public void enqueue(E x);
  58.  
  59.     // Go dodava x na kraj od redicata.
  60.  
  61.     public E dequeue();
  62.     // Go otstranuva i vrakja pochetniot element na redicata.
  63.  
  64. }
  65.  
  66. class LinkedQueue<E> implements Queue<E> {
  67.  
  68.     // Redicata e pretstavena na sledniot nacin:
  69.     // length go sodrzi brojot na elementi.
  70.     // Elementite se zachuvuvaat vo jazli dod SLL
  71.     // front i rear se linkovi do prviot i posledniot jazel soodvetno.
  72.     SLLNode<E> front, rear;
  73.     int length;
  74.  
  75.     // Konstruktor ...
  76.  
  77.     public LinkedQueue() {
  78.         clear();
  79.     }
  80.  
  81.     public boolean isEmpty() {
  82.         // Vrakja true ako i samo ako redicata e prazena.
  83.         return (length == 0);
  84.     }
  85.  
  86.     public int size() {
  87.         // Ja vrakja dolzinata na redicata.
  88.         return length;
  89.     }
  90.  
  91.     public E peek() {
  92.         // Go vrakja elementot na vrvot t.e. pocetokot od redicata.
  93.         if (front == null)
  94.             throw new NoSuchElementException();
  95.         return front.element;
  96.     }
  97.  
  98.     public void clear() {
  99.         // Ja prazni redicata.
  100.         front = rear = null;
  101.         length = 0;
  102.     }
  103.  
  104.     public void enqueue(E x) {
  105.         // Go dodava x na kraj od redicata.
  106.         SLLNode<E> latest = new SLLNode<E>(x, null);
  107.         if (rear != null) {
  108.             rear.succ = latest;
  109.             rear = latest;
  110.         } else
  111.             front = rear = latest;
  112.         length++;
  113.     }
  114.  
  115.     public E dequeue() {
  116.         // Go otstranuva i vrakja pochetniot element na redicata.
  117.         if (front != null) {
  118.             E frontmost = front.element;
  119.             front = front.succ;
  120.             if (front == null)
  121.                 rear = null;
  122.             length--;
  123.             return frontmost;
  124.         } else
  125.             throw new NoSuchElementException();
  126.     }
  127.  
  128. }
  129.  
  130. class Graph<E> {
  131.  
  132.     int num_nodes; // broj na jazli
  133.     E nodes[]; // informacija vo jazlite - moze i ne mora?
  134.     int adjMat[][]; // matrica na sosednost
  135.  
  136.     @SuppressWarnings("unchecked")
  137.     public Graph(int num_nodes) {
  138.         this.num_nodes = num_nodes;
  139.         nodes = (E[]) new Object[num_nodes];
  140.         adjMat = new int[num_nodes][num_nodes];
  141.  
  142.         for (int i = 0; i < this.num_nodes; i++)
  143.             for (int j = 0; j < this.num_nodes; j++)
  144.                 adjMat[i][j] = 0;
  145.     }
  146.  
  147.     int adjacent(int x, int y) { // proveruva dali ima vrska od jazelot so
  148.         // indeks x do jazelot so indeks y
  149.         return (adjMat[x][y] != 0) ? 1 : 0;
  150.     }
  151.  
  152.     void addEdge(int x, int y) { // dodava vrska megu jazlite so indeksi x i y
  153.         adjMat[x][y] = 1;
  154.        
  155.     }
  156.  
  157.     void deleteEdge(int x, int y) {
  158.         // ja brise vrskata megu jazlite so indeksi x i y
  159.         adjMat[x][y] = 0;
  160.         adjMat[y][x] = 0;
  161.     }
  162.  
  163.     E get_node_value(int x) { // ja vraka informacijata vo jazelot so indeks x
  164.         return nodes[x];
  165.     }
  166.  
  167.     void set_node_value(int x, E a) { // ja postavuva informacijata vo jazelot
  168.         // so indeks na a
  169.         nodes[x] = a;
  170.     }
  171.  
  172.     @Override
  173.     public String toString() {
  174.         String ret = "  ";
  175.         for (int i = 0; i < num_nodes; i++)
  176.             ret += nodes[i] + " ";
  177.         ret += "\n";
  178.         for (int i = 0; i < num_nodes; i++) {
  179.             ret += nodes[i] + " ";
  180.             for (int j = 0; j < num_nodes; j++)
  181.                 ret += adjMat[i][j] + " ";
  182.             ret += "\n";
  183.         }
  184.         return ret;
  185.     }
  186.  
  187.     public void printMatrix() {
  188.         for (int i = 0; i < num_nodes; i++) {
  189.             for (int j = 0; j < num_nodes; j++)
  190.                 System.out.print(adjMat[i][j] + " ");
  191.             System.out.println();
  192.         }
  193.     }
  194.     public static int counter = 0;
  195.  
  196.     public void dfs_visit(boolean[] visited, int node){
  197.         if(!visited[node]){
  198.  
  199.             visited[node] = true;
  200.             this.counter++;
  201.             for(int i = 0; i < num_nodes; i++){
  202.                 if(adjacent(node,i) == 1){
  203.                     if(!visited[i]){
  204.                         dfs_visit(visited,i);
  205.                     }
  206.                 }
  207.             }
  208.  
  209.         }
  210.     }
  211.  
  212.  
  213.     public int sendFishes(int start) {
  214.         //VASIOT KOD OVDE, ILI TAMU, VAS IZBOR
  215.  
  216.  
  217.  
  218.         boolean visited[] = new boolean[this.num_nodes];
  219.         for(int i = 0; i < num_nodes;i++){
  220.             visited[i] = false;
  221.         }
  222.  
  223.  
  224.         visited[start] = true;
  225.  
  226.         for(int i = 0; i < num_nodes; i++){
  227.             if(adjacent(start,i) == 1){
  228.                 if(!visited[i]){
  229.                     dfs_visit(visited,i);
  230.                 }
  231.             }
  232.         }
  233.  
  234.         return this.counter;
  235.     }
  236. }
  237.  
  238. public class DedoMrazIRibite {
  239.  
  240.     public static void main(String[] args) {
  241.         Scanner in = new Scanner(System.in);
  242.         int N = in.nextInt();
  243.         int U = in.nextInt();
  244.         Graph<Integer> g = new Graph<>(N);
  245.         for (int i = 0; i < U; i++) {
  246.             int r = in.nextInt();
  247.             int q = in.nextInt();
  248.             g.addEdge(r, q);
  249.  
  250.         }
  251.         int L = in.nextInt();
  252.         System.out.println(g.sendFishes(L));
  253.         System.out.println("Srekna Nova Godina");
  254.         in.close();
  255.     }
  256.  
  257. }
RAW Paste Data