Skip to content

Instantly share code, notes, and snippets.

@StevenConradEllis
Last active October 2, 2019 20:24
Show Gist options
  • Save StevenConradEllis/7877c4881c82fa0d01bc72a70ad2f3f5 to your computer and use it in GitHub Desktop.
Save StevenConradEllis/7877c4881c82fa0d01bc72a70ad2f3f5 to your computer and use it in GitHub Desktop.
Social Network Dynamic Connectivity
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Social {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File("/Users/steven/demo/friends.txt"));
int n = 100; // 100 individuals
WeightedQuickUnion wqu = new WeightedQuickUnion(n);
long startTime = System.nanoTime();
String earliestTime = null;
while (in.hasNext() && earliestTime == null) {
String[] p = in.next().split("\\|");
String timeConnected = p[0];
int userId1 = Integer.valueOf(p[1]);
int userId2 = Integer.valueOf(p[2]);
if (!wqu.connected(userId1, userId2)) {
wqu.union(userId1, userId2);
}
if (wqu.count() == 1){
earliestTime = timeConnected;
}
}
long endTime = System.nanoTime();
long elapsedTime = endTime - startTime;
System.out.println(" earliest timestamp : " + earliestTime);
System.out.println(" Execution time for quick find in milliseconds : " + elapsedTime / 1000000);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment