Navigation Menu

Skip to content

Instantly share code, notes, and snippets.

@lucasklaassen
Created April 17, 2020 18:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lucasklaassen/6867b5ee4509378efec58de97890a7ff to your computer and use it in GitHub Desktop.
Save lucasklaassen/6867b5ee4509378efec58de97890a7ff to your computer and use it in GitHub Desktop.
Algorithms 1 Union-find with specific canonical element
public class Canonical {
private int members[];
public void setMembers(int members[]) {
this.members = members;
}
private int findRoot(int memberId) {
boolean foundRoot = false;
int rootId = memberId;
while(!foundRoot) {
int newId = this.members[rootId];
if(newId == this.members[newId]) {
foundRoot = true;
}
rootId = newId;
}
return rootId;
}
public void union(int memberId, int memberIdToUnion) {
int rootMemberId = findRoot(memberId);
int rootMemberIdToUnion = findRoot(memberIdToUnion);
if(rootMemberId >= rootMemberIdToUnion) {
this.members[rootMemberIdToUnion] = rootMemberId;
} else {
this.members[rootMemberId] = rootMemberIdToUnion;
}
}
public boolean connected(int memberId, int memberIdToCheck) {
int rootMemberId = findRoot(memberId);
int rootMemberIdToCheck = findRoot(memberIdToCheck);
return rootMemberId == rootMemberIdToCheck;
}
public int find(int memberId) {
return findRoot(memberId);
}
}
public class TestRunner2 {
public static void main(String[] args) {
Canonical percolation = new Canonical();
percolation.setMembers(new int[]{ 0,1,2,3,4,5,6,7,8,9,10 });
percolation.union(3,6);
percolation.union(5,7);
percolation.union(1,10);
percolation.union(6,5);
percolation.union(1,7);
percolation.union(2,8);
System.out.println(percolation.connected(6,3));
System.out.println(percolation.connected(0,3));
System.out.println(percolation.find(7));
System.out.println(percolation.find(0));
}
}
@manhha1995
Copy link

thanks for your attribution

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment