Advertisement
Guest User

Untitled

a guest
Dec 14th, 2019
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.10 KB | None | 0 0
  1. import java.util.*;
  2.  
  3.  
  4.  
  5. public class Komponentit {
  6.  
  7.  
  8.  
  9. static int n;
  10.  
  11. static int[] vanhempi;
  12.  
  13. static int[] koko;
  14.  
  15. static int ulos;
  16.  
  17.  
  18.  
  19.  
  20.  
  21. public Komponentit(int n) {
  22.  
  23. ulos = n;
  24.  
  25. vanhempi = new int[n+1];
  26.  
  27. koko = new int[n+1];
  28.  
  29. for (int i = 1; i <= n; i++) {
  30.  
  31. vanhempi[i] = i;
  32.  
  33. koko[i] = 1;
  34.  
  35. }
  36.  
  37. }
  38.  
  39.  
  40.  
  41. static int etsiHuippu(int x) {
  42.  
  43. while (vanhempi[x] != x) {
  44.  
  45. x = vanhempi[x];
  46.  
  47. }
  48.  
  49. return x;
  50.  
  51. }
  52.  
  53.  
  54.  
  55. public void yhdista(int a, int b) {
  56.  
  57. a = etsiHuippu(a);
  58.  
  59. b = etsiHuippu(b);
  60.  
  61. if (a == b) {
  62.  
  63. return;
  64.  
  65. }
  66.  
  67. if (koko[a] > koko[b]) {
  68.  
  69. vanhempi[b] = a;
  70.  
  71. koko[a] += koko[b];
  72.  
  73. ulos--;
  74.  
  75. } else {
  76.  
  77. vanhempi[a] = b;
  78.  
  79. koko[b] += koko[a];
  80.  
  81. ulos--;
  82.  
  83. }
  84.  
  85.  
  86.  
  87.  
  88.  
  89. }
  90.  
  91.  
  92.  
  93. public int laske() {
  94.  
  95. return ulos;
  96.  
  97. }
  98.  
  99.  
  100.  
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement