Coursera Algorithms week1 查并集练习测验：1 Social network connectivity

题目原文描述：

Given a social network containing. n members and a log file containing

分析：

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

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

 1 import java.io.FileInputStream;
 2 import java.io.FileNotFoundException;
 3 import java.util.Scanner;
 4 
 5 import edu.princeton.cs.algs4.StdOut;
 6 import edu.princeton.cs.algs4.WeightedQuickUnionUF;
 7 
 8 
 9 public class SocialNetworkConnUF {
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     }
41     public static void main(String[] args){
42         FileInputStream ins;
43         try {
44             ins = new FileInputStream("socialNetworkLog.txt");
45             SocialNetworkConnUF socialNet = new SocialNetworkConnUF(10, ins);
46             String earliestConnTime = socialNet.getEarliestConTime();
47             StdOut.println(" the earliest connected time is :" + earliestConnTime);
48         } catch (FileNotFoundException e) {
49             e.printStackTrace();
50         }
51         
52     }
53     /*
54      * socialNetworkLog.txt
55      * 20170714001 0 1
56      * 20170714002 4 5
57      * 20170714003 8 9
58      * 20170714004 2 4
59      * 20170714005 5 6
60      * 20170714006 7 8
61      * 20170714007 2 5
62      * 20170714008 6 7
63      * 20170714009 1 2
64      * 20170714010 0 3
65      * 20170714011 1 9
66      * 20170714012 3 7
67      *
68      */
69 }

Coursera Algorithms week1 查并集 练习测验：1 Social network connectivity

推荐阅读

Coursera Algorithms week1 查并集练习测验：1 Social network connectivity