WallHero

Union Find Java

Sep 5th, 2020
1,521
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.Scanner;
  2.  
  3. public class UnionFind {
  4.  
  5.     static Scanner scan = new Scanner(System.in);
  6.     final static int maxnodos = (int) (1e6+1);
  7.    
  8.     static int[] altura = new int[maxnodos+1];
  9.     static int[] padre = new int[maxnodos+1];
  10.    
  11.     static void init()
  12.     {
  13.         for(int i = 1; i <= maxnodos; i++)
  14.         {
  15.             altura[i] = 1;
  16.             padre[i] = i;
  17.         }
  18.     }
  19.    
  20.     static int find(int a)
  21.     {
  22.         int retValue = padre[a];
  23.         if(padre[a] != a)
  24.         {
  25.             retValue = find(padre[a]);
  26.         }
  27.         padre[a] = retValue;
  28.         return retValue;
  29.     }
  30.    
  31.     static boolean check(int a , int b)
  32.     {
  33.         return find(a) == find(b);
  34.     }
  35.    
  36.     static void union(int a, int b)
  37.     {
  38.         a = find(a);
  39.         b = find(b);
  40.         if(a == b) return;
  41.         if(altura[b]> altura[a])
  42.         {
  43.             int t = b;
  44.             b = a;
  45.             a = t;
  46.         }
  47.         padre[b]= a;
  48.         altura[a]+= altura[b];
  49.     }
  50.    
  51.     public static void main(String[] args) {
  52.        
  53.         char x;
  54.         int a, b;
  55.         init();
  56.         while((x= scan.next().charAt(0)) != 'F')
  57.         {
  58.             a = scan.nextInt();
  59.             b = scan.nextInt();
  60.             if(x == 'P') System.out.println(check(a, b) ? "S" : "N");
  61.             else union(a, b);
  62.         }
  63.  
  64.     }
  65.  
  66. }
  67.  
RAW Paste Data