Description
You have a social network containing N members. Use N=1000 for the final version. Friendships form randomly, one each day. Implement an algorithm to determine when all members are connected (i.e, every member is a friend of a friend of a friend…of a friend). Output the number of days required.
Be sure to implement a Union-Find class which is reusable. Perform union by height and path compression (during finds). In order to verify this is working correctly, print the contents of the data structure periodically to make sure it works properly.
We think that path compression gives almost constant time. So you should see a simple relationship between the number of unions and the recursive count of finds. In order to verify this, output the following:
- The total number of unions that are performed (each union does two finds).
- The total number of times find was called. Since find is recursive, the total number of times the routine is called will give us a measure of work.
Hints:
- A “new” friendship may not change the disjoint sets. That is okay. That friendship still “counts” as the friendship for the day.
- If two members are already in the same set, do NOT link them again. That could invalidate the data values.
- It is useful if the union tells you whether or not the items were already in the same set. We say a union is “successful” if it joins two members who were not already connected.
- To join n different elements (via union), you need (n-1) successful unions.
