SHARE
TWEET

Untitled

a guest May 24th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6.    
  7. package javaapplication39;
  8.  
  9. import java.io.BufferedReader;
  10. import java.io.File;
  11. import java.io.FileReader;
  12. import java.io.IOException;
  13. import java.io.InputStreamReader;
  14. import static java.lang.Math.abs;
  15. import static java.lang.Math.abs;
  16. import java.util.Arrays;
  17. import java.lang.Object;
  18. import java.util.Collections;
  19. import java.util.Comparator;
  20.  
  21. public class JavaApplication39 {
  22.     static int[] cesta;
  23.     public static int[] komponenty;
  24.     static int velikost, pocetVrcholu, pocetHran, i, j, delka;
  25.  
  26.     public static void main(String args[]) throws IOException {
  27.         int[] pole;
  28.  
  29.         //File f = new File("a.txt");
  30.  
  31.         //BufferedReader in = new BufferedReader(new FileReader(f));
  32.         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  33.         String line = in.readLine();// preskoceni radku
  34.         velikost = Integer.parseInt(line);
  35.         delka  = velikost * velikost;
  36.         pole = new int[delka];
  37.         int index = 0;
  38.         while ((line = in.readLine()) != null) {
  39.             String[] casti = line.split(" ");
  40.             for (int i = 0; i < velikost; i++) {
  41.                 pole[index] = Integer.parseInt(casti[i]);
  42.                 index++;
  43.             }
  44.             if (index == delka) {
  45.                 break;
  46.             }
  47.         }
  48.         pocetVrcholu = delka;
  49.  
  50.         komponenty = new int[pocetVrcholu];
  51.         for (int i = 0; i < komponenty.length; i++) {
  52.             komponenty[i] = i;
  53.         }
  54.         pocetHran = (velikost + velikost) * (velikost - 1);
  55.         cesta = new int[pocetVrcholu + 1];
  56.         Hrana e[] = new Hrana[pocetHran];
  57.         Hrana t = new Hrana();
  58.         int hrana = 0;
  59.         for (int i = 1; i < pole.length; i++) {
  60.             if (i % velikost != 0) {
  61.                 e[hrana] = new Hrana();
  62.                 e[hrana].odkud = i - 1;
  63.                 e[hrana].kam = i;
  64.                 e[hrana].vaha = abs(pole[i] - pole[i - 1]);
  65.                 hrana++;
  66.             }
  67.             if (i >= velikost) {
  68.                 e[hrana] = new Hrana();
  69.                 e[hrana].odkud = i - velikost;
  70.                 e[hrana].kam = i;
  71.                 e[hrana].vaha = abs(pole[i] - pole[i - velikost]);
  72.                 hrana++;
  73.             }
  74.         }
  75.         Arrays.sort(e);
  76.        
  77.         for (i = 0; i < pocetVrcholu; i++) {
  78.             cesta[i] = 0;
  79.         }
  80.  
  81.         i = 0;
  82.         j = 0;
  83.  
  84.         Hrana kostra[] = new Hrana[pocetVrcholu - 1];
  85.         int max = 0;
  86.         while ((i != pocetVrcholu - 1) && (j != pocetHran)) {
  87.             if (jeCyklus(e[j])) {
  88.                 kostra[i] = new Hrana();
  89.                 kostra[i].odkud = e[j].odkud;
  90.                 kostra[i].kam = e[j].kam;
  91.                 kostra[i].vaha = e[j].vaha;
  92.                 max = e[j].vaha;
  93.                 i++;
  94.             }
  95.             j++;
  96.         }
  97.  
  98.         for (int i = 0; i < kostra.length; i++) {
  99.             if (max != kostra[i].vaha) {
  100.                 pridatHranu(kostra[i].odkud, kostra[i].kam);
  101.             }
  102.         }
  103.         Vypis(komponenty, velikost);
  104.     }
  105.  
  106.     public static boolean jeCyklus(Hrana e) {
  107.         int u = e.odkud, v = e.kam;
  108.         while (cesta[u] > 0) {
  109.             u = cesta[u];
  110.         }
  111.         while (cesta[v] > 0) {
  112.             v = cesta[v];
  113.         }
  114.         if (u != v) {
  115.             cesta[u] = v;
  116.             return true;
  117.         }
  118.         return false;
  119.     }
  120.  
  121.     static class Hrana implements Comparable<Hrana>{
  122.         int odkud, kam, vaha;
  123.         public Integer getVaha() {
  124.             return vaha;
  125.         }
  126.         @Override
  127.         public int compareTo(Hrana o) {
  128.             return this.getVaha().compareTo(o.getVaha());
  129.         }  
  130.     }
  131.  
  132.     public static void Vypis(int[] pole, int delka) {
  133.         System.out.println(delka);
  134.         for (int i = 0; i < pole.length; i++) {
  135.             if (pole[i] == 0) {
  136.                 System.out.printf("  0 ");
  137.             } else {
  138.                 System.out.printf("  1 ");
  139.             }
  140.             if ((i + 1) % velikost == 0) {
  141.                 System.out.println("");
  142.             }
  143.         }
  144.     }
  145.  
  146.     public static void pridatHranu(int index1, int index2) {
  147.         int temp = komponenty[index1];
  148.         int temp2 = komponenty[index2];
  149.         for (int i = 0; i < komponenty.length; i++) {
  150.             if (komponenty[i] == temp2) {
  151.                 komponenty[i] = temp;
  152.             }
  153.         }
  154.     }
  155. }
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