Created
March 17, 2019 14:29
-
-
Save wyukawa/6c98ffc8dc9f318ee6d71971e093bae1 to your computer and use it in GitHub Desktop.
This file contains hidden or 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
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