Union-find expressed as a social network

Question

This is an interview question that I am trying to answer:

Given a social network containing N members and a log file containing M timestamps at which times pairs of members formed friendships, design an algorithm to determine the earliest time at which all members are connected (i.e, every member is a friend of a friend of a friend...of a friend). Assume that the log file is sorted by timestamp and that friendship is an equivalence relation. The running time of your algorithm should be M log N or better and use extra space proportional to N.

The first thing I thought was..."I can't do this!".

But then I thought how can this social network be expressed as a data structure. Union-find is a data structure that can be used. Now I have to understand what it means when all members are connected. How can I view the actual data structure and what it looks like when every member became friends with each other?

I think only until I can understand visually or conceptually how the system becomes fully connected can I begin to figure out how to find the timestamp that corresponds with that event.

Answer 1

When you add a friendship to the union-find datastructure, you can note if it results in two graph components being joined. Simply keep adding edges until N-1 of these merging events have happened.

In pseudo-code form:

G := UnionFind(1..N) count := 0 for timestamp, p1, p2 in friendships {     if G.Find(p1) != G.Find(p2) {         G.Union(p1, p2)         count++         if count == N-1 {             return timestamp         }     } } return +infinity 

Answer 2

Ok to solve this exercise I did the assumption that the log file will look something like this:

0 1 2015-08-14 18:00:00 1 9 2015-08-14 18:01:00 0 2 2015-08-14 18:02:00 0 3 2015-08-14 18:04:00 0 4 2015-08-14 18:06:00 0 5 2015-08-14 18:08:00 0 6 2015-08-14 18:10:00 0 7 2015-08-14 18:12:00 0 8 2015-08-14 18:14:00 1 2 2015-08-14 18:16:00 1 3 2015-08-14 18:18:00 1 4 2015-08-14 18:20:00 1 5 2015-08-14 18:22:00 2 1 2015-08-14 18:24:00 2 3 2015-08-14 18:26:00 2 4 2015-08-14 18:28:00 5 5 2015-08-14 18:30:00 

---

Where the 2 first numbers are the members who formed the friendship follow by the timestamp.

Another important thing to call out is that the exercise mention that the the file is sorted, so I have decide to sort it on a ascending order.

With this information, you can use the WeightedQuickUnionFind data structure provided in the class and simple process the file performing union operation on the members, once that you make the union you can ask for how many components are in the structure, if there is only one that means all members have equivalent relation.

Here is the code I did:

public static void main(String[] args) {          int n = StdIn.readInt();         WeightedQuickUnion uf = new WeightedQuickUnion(n);         String date, time;         //timestamps are sorted ascending         while (!StdIn.isEmpty()) {              int p = StdIn.readInt();             int q = StdIn.readInt();             date = StdIn.readString();             time = StdIn.readString();               uf.union(p, q);              StdOut.println("["+p+","+q+"]");              if(uf.getComponents() == 1){                 StdOut.println("All members were connected at: " + date + time);                 break;             }          } 

---

The performance will be M lg N because you are iterating M times (the amount of lines in the log file) and the union operations takes: lg n.