Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Komponentit {
- static int n;
- static int[] vanhempi;
- static int[] koko;
- static int ulos;
- public Komponentit(int n) {
- ulos = n;
- vanhempi = new int[n+1];
- koko = new int[n+1];
- for (int i = 1; i <= n; i++) {
- vanhempi[i] = i;
- koko[i] = 1;
- }
- }
- static int etsiHuippu(int x) {
- while (vanhempi[x] != x) {
- x = vanhempi[x];
- }
- return x;
- }
- public void yhdista(int a, int b) {
- a = etsiHuippu(a);
- b = etsiHuippu(b);
- if (a == b) {
- return;
- }
- if (koko[a] > koko[b]) {
- vanhempi[b] = a;
- koko[a] += koko[b];
- ulos--;
- } else {
- vanhempi[a] = b;
- koko[b] += koko[a];
- ulos--;
- }
- }
- public int laske() {
- return ulos;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement