Algorithms, Part I -- Social Network Connectivity (With Union-Find) | Data Nest

Algorithms, Part I — Social Network Connectivity (With Union-Find) | Data Nest
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.

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 theUnion-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 members are connected, which means very time we union two objects, we have to check if all points are connected.

https://www.cnblogs.com/evasean/p/7204525.html

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.

分析：

题目的意思是有一个包含n个成员的社交网络，日志文件log按照时间戳顺序存储了两个成员之间成为朋友的时间，共有m条记录。让我们设计一个算法来根据这个log文件来计算m个成员全部通过朋友关系连通的时间。

这是个典型的并查集。思路是读取日志文件，遍历文件记录，逐条记录union。采用加权quick-union算法，就可以满足mlogn的复杂度要求。作业提交100

10     private FileInputStream ins;
11     private WeightedQuickUnionUF uf;
12     public SocialNetworkConnUF(int num, FileInputStream ins){
13         this.ins = ins;
14         uf = new WeightedQuickUnionUF(num);
15     }
16     
17     @SuppressWarnings("resource")
18     public String getEarliestConTime(){
19         Scanner scanner = new Scanner(ins,"utf-8");
20         String earliestConTime = null;
21         while(scanner.hasNextLine()){
22             String line = scanner.nextLine();
23             if(line != null && !line.trim().equals("")){
24                 String[] lineArray = line.split(" ");
25                 if(lineArray.length == 3){
26                     String timestamp = lineArray[0];
27                     int p = Integer.parseInt(lineArray[1]);
28                     int q = Integer.parseInt(lineArray[2]);
29                     if(uf.connected(p, q)) continue;
30                     uf.union(p,q);
31                     if(uf.count() == 1) {
32                         earliestConTime = timestamp;
33                         break;
34                     }
35                 }
36             }
37             
38         }
39         return earliestConTime;
40     }

https://shadowoom123.wordpress.com/2018/04/04/coursera-algorithm-1-union-find-practice-problems-social-network-connectivity/
https://raw.githubusercontent.com/eschwabe/interview-practice/master/coursera/algorithms-part1/union-find/SocialNetworkConnectivity.java

  private UnionFindUF uf;
  private int numComponents;

  public SocialNetworkConnectivity(int N) {
    uf = new QuickFindUF(N);
    numComponents = N;
  }

  public void addFriendship(int p1, int p2) {
    if (!uf.connected(p1, p2)) {
      --numComponents;
    }
    uf.union(p1,p2);
  }

  public boolean fullyConnected() {
    return this.numComponents == 1;
  }

https://gist.github.com/jingz8804/9026118
Well, if we use the naive Union-Find algorithm as a base, to check if all objects are connected is to check if they have the same group label in the array and that will take O(N) time for each union. So M unions take O(MN), which is unacceptable.

https://github.com/guibin/Knowledge/blob/master/libs/lib.algorithm/src/main/java/guibin/zhang/onlinecourse/SocialNetworkConnectivity.java

http://mayalin.gitbooks.io/algorithms-part-i/content/chapter6.html
Read full article from Algorithms, Part I — Social Network Connectivity (With Union-Find) | Data Nest