Nice blog post about “Social network connectivity” problem that appears in Coursera Algorithms I (https://class.coursera.org/algs4partI-009)
Q: 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 MlogN or better and use extra space proportional to N.
(Java Code on github at the bottom of the post. )
My thoughts and solutions:
When solving dynamic connectivity problems (like whether there is a path between two nodes but we don’t care what the exact path is), we can try using the Union-Find algorithm. And this is a typical application of union-find in social network.
This question asks if we can determine the earliest time at which all…
View original post 391 more words