Skip to content

Instantly share code, notes, and snippets.

@wyukawa
Created March 17, 2019 14:29
Show Gist options
  • Save wyukawa/6c98ffc8dc9f318ee6d71971e093bae1 to your computer and use it in GitHub Desktop.
Save wyukawa/6c98ffc8dc9f318ee6d71971e093bae1 to your computer and use it in GitHub Desktop.
col=1 col=2 col=3 col=4
row=1 0 1 2 3 4
row=2 5 6 7 8 9
...
1,2,,,,n
For example, here is a log file.
First/Second column is member id.
Third column is a timestamp
1 2 201903161010
2 3 201903161011
...
code is something like this.
If we use a weithted quick-union, running time of union method is logn
checkAllMembersConnected is also logn but unfortunately I can't explain clearly...
Anyway all running time is at most mlogn
for(int i=0; i<m; i++) {
union(firstMembers[i], secondMembers[i]);
if(checkAllMembersConnected()) {
return timestamp[i];
break;
}
}
private int[] firstMembers;
private int[] secondMembers;
private int[] timestamp;
for(int i=0; i<m; i++) {
union(firstMembers[i], secondMembers[i]);
if(checkAllMembersConnected()) {
return timestamp[i];
break;
}
}
public boolean checkAllMembersConnected() {
boolean allMembersConnectedFlag=true
for(int i=0; i<n-1; i++) {
if(!connected(i, i+1)) {
allMembersConnectedFlag=false;
break;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment