Last active
April 17, 2020 01:07
-
-
Save lucasklaassen/a6019cb9cf5d9fc8223c596811ae5762 to your computer and use it in GitHub Desktop.
Algorithms 1 Social network connectivity
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
import java.util.EmptyStackException; | |
import java.util.HashMap; | |
class MemberLogItem { | |
public int timestamp = 0; | |
public int follower = 0; | |
public int followee = 0; | |
public MemberLogItem(int timestamp, int follower, int followee) { | |
this.timestamp = timestamp; | |
this.follower = follower; | |
this.followee = followee; | |
} | |
} | |
public class Percolation { | |
private int members[] = new int[]{ 1,2,3,4,5,6,7,8,9,10 }; | |
private int numberOfRoots = members.length; | |
private MemberLogItem[] memberLogItems; | |
private HashMap<Integer, Integer> memberRelations = new HashMap<Integer, Integer>(); | |
public void setMemberLogItems(MemberLogItem[] memberLogItems) { | |
this.memberLogItems = memberLogItems; | |
} | |
private int findRoot(int memberId) { | |
boolean foundRoot = false; | |
int rootId = memberId; | |
while(!foundRoot) { | |
int newId = memberRelations.get(rootId); | |
if(newId == memberRelations.get(newId)) { | |
foundRoot = true; | |
} | |
rootId = newId; | |
} | |
return rootId; | |
} | |
private void makeFriends(int follower, int followee) { | |
int followerRoot = findRoot(follower); | |
int followeeRoot = findRoot(followee); | |
if(followerRoot != followeeRoot) { | |
numberOfRoots--; | |
memberRelations.put(followerRoot, followeeRoot); | |
} | |
} | |
public int solve() { | |
for(int i = 0; i < memberLogItems.length; i++) { | |
MemberLogItem memberLogItem = memberLogItems[i]; | |
Integer followerRelation = memberRelations.get(memberLogItem.follower); | |
if(followerRelation == null) { | |
memberRelations.put(memberLogItem.follower, memberLogItem.follower); | |
} | |
Integer followeeRelation = memberRelations.get(memberLogItem.followee); | |
if(followeeRelation == null) { | |
memberRelations.put(memberLogItem.followee, memberLogItem.followee); | |
} | |
makeFriends(memberLogItem.follower, memberLogItem.followee); | |
if(numberOfRoots == 1) { | |
return memberLogItem.timestamp; | |
} | |
} | |
// If this error gets thrown, no solutions were found. | |
throw new EmptyStackException(); | |
} | |
} | |
public class TestRunner { | |
public static void main(String[] args) { | |
Percolation percolation = new Percolation(); | |
final MemberLogItem[] memberLogItems = new MemberLogItem[12]; | |
memberLogItems[0] = new MemberLogItem(1234, 1, 5); | |
memberLogItems[1] = new MemberLogItem(1235, 2, 3); | |
memberLogItems[2] = new MemberLogItem(1236, 1, 6); | |
memberLogItems[3] = new MemberLogItem(1237, 5, 7); | |
memberLogItems[4] = new MemberLogItem(1238, 9, 4); | |
memberLogItems[5] = new MemberLogItem(1239, 8, 2); | |
memberLogItems[6] = new MemberLogItem(1240, 10, 1); | |
memberLogItems[7] = new MemberLogItem(1241, 5, 3); | |
memberLogItems[8] = new MemberLogItem(1242, 3, 8); | |
memberLogItems[9] = new MemberLogItem(1243, 9, 1); | |
memberLogItems[10] = new MemberLogItem(1244, 9, 2); | |
memberLogItems[11] = new MemberLogItem(1245, 9, 3); | |
percolation.setMemberLogItems(memberLogItems); | |
System.out.println(percolation.solve()); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment