001package net.automatalib.commons.util.combinatorics; 002 003public class DisjointSetForestInt { 004 005 006 private int[] parent; 007 private int[] rank; 008 009 public DisjointSetForestInt(int initSize) { 010 this.parent = new int[initSize]; 011 for(int i = 0; i < this.parent.length; i++) 012 this.parent[i] = -1; 013 this.rank = new int[initSize]; 014 } 015 016 017 public int find(int a) { 018 int p = parent[a]; 019 if(p == -1) 020 return a; 021 p = find(p); 022 parent[a] = p; 023 return p; 024 } 025 026 public int union(int a, int b) { 027 return directUnion(find(a), find(b)); 028 } 029 030 public int directUnion(int a, int b) { 031 assert parent[a] == -1 && parent[b] == -1; 032 033 if(a == b) 034 return a; 035 036 int ra = rank[a], rb = rank[b]; 037 if(ra < rb) { 038 parent[a] = b; 039 return b; 040 } 041 if(ra == rb) { 042 rank[a]++; 043 } 044 parent[b] = a; 045 return a; 046 } 047 048 public int size() { 049 return parent.length; 050 } 051 052 053}