ledcode-そして検索集

を実施します

parent：各ノードの親ノード

を記録する。

size：各ツリーの重さを記録し、union後のツリーのバランスを維持することが目的です。

パス圧縮：任意の数の高さが定数

であることを保証する。

public class UF {
	 //       
	 private int count;
	 //      
	 private int[] parent;
	 //       (               )
	 private int[] size;

	 public UF(int n) {
		  this.count = n;
		  //            
		  //        1
		  parent = new int[n];
		  size = new int[n];
		  for(int i = 0; i < n; i++) {
			   parent[i] = i;
			   size[i] = 1;
		  }
	 }

	 //      
	 private int find(int x) {
		  while(parent[x] != x) {
			   //     (        )
			   parent[x] = parent[parent[x]];
			   x = parent[x];
		  }
		  return x;
	 }

	 //   
	 public void union(int p, int q) {
		  int rootP = find(p);
		  int rootQ = find(q);
		  if(rootP == rootQ) {
			   return;
		  }
  
		  //         
		  if(size[rootP] > size[rootQ]) {
			   parent[rootQ] = rootP;
			   size[rootP] += size[rootQ];
		  }else {
			   parent[rootP] = rootQ;
			   size[rootQ] += size[rootP];
		  }
  
		  count--;
	 }
 
	  //       
	 public boolean connected(int p, int q) {
		  int rootP = find(p);
		  int rootQ = find(q);
		  return rootP == rootQ;
	 }
 
	 public int count() {
		  return count;
	 }
}	 

適用

方程式の適合性（ledcode-990）

    public boolean equationsPossible(String[] equations) {
	     UF uf = new UF(26);
     
	     for(String s : equations) {
		      if(s.charAt(1) == '=') {
			       uf.union(s.charAt(0) - 'a', s.charAt(3) - 'a');
		      }
	     }
	     for(String s : equations) {
		      if(s.charAt(1) == '!') {
			       if(uf.connected(s.charAt(0) - 'a', s.charAt(3) - 'a')) {
				        return false;
			       }
		      }
	     }
     
     
	     return true;
  }