Created
April 17, 2020 18:21
-
-
Save lucasklaassen/6867b5ee4509378efec58de97890a7ff to your computer and use it in GitHub Desktop.
Algorithms 1 Union-find with specific canonical element
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
thanks for your attribution