并查集作业和一些想法
三个简述题
ENGLISH
Q1:Question 1
Social network connectivity. 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 logm logn or better and use extra space proportional to n.
A1:We can solve this problem using the weighted quick union algorithm. When initialized, the n members are each in an independent group, and count=n is recorded as the current remaining continuous flux. The weighted union operation is performed each time a log is read, and the remaining continued flux is reduced by 1. When the remaining flux drops to 1, the earliest connection time is the current log time。
Q2:Union-find with specific canonical element. Add a method find() to the
find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better.For example, if one of the connected components is {1,2,6,9}{1,2,6,9}, then the find method should return 99 for each of the four elements in the connected components.
A2:We use the weighted quick-union algorithm to solve this problem. When initialized, each data is independent as a group, we define two arrays: arr records the maximum number of each group, arr[i]=i.; sz[i]=1 is the current size of each set of trees. Update arr[Root node of a larger tree] =max(arr[root(p)],arr[root(q)]) when performing the union operation, that is, when connecting a small tree to a large tree. When performing the find (i) operation, return the value of arr[root(i)]
Q3:Successor with delete.Given a set of n integers ={0,1,…,N-1}.S={0,1,…,n−1} and a sequence of requests of the following form:
- Remove x from S
- Find the successor of x: the smallest y in S such that y≥x.
design a data type so that all operations (except construction) take logarithmic time or better in the worst case.
A3:We use quick-union with compression. Design two arrays: parent[], to record the data set, initialized with each element pointing to itself; next[] Record the next successsor for i. When remove x from s is executed, the collection to which x belongs is first pointed to next[next[i]] by uinon(x, next[i]). We optimize the algorithm with path compression when merging the two collections. When we find the current successor to x, return the value next[root[x]]. So we’re going to have a logarithmic complexity
通过并查集模拟渗流问题(ddl: 4.14)
这是Coursera留下的并查集大作业
渗流模型简述:在给定的n*n网格中,每一个格点有三个状态(关、开、充满水),当水流自上而下能够流通网格时(水的流通方向为上下左右),该模型处于渗流状态。
问题简述:数学家发现当每个格点打开的概率为p,存在一个阈值p ,当n最足够大时,所有p>p 的模型几乎都处于渗流,而所有p<p 的模型几乎处于阻塞状态。然而数学家无法运用数理方法准确估计p 的值。现在我们在计算机上设计程序模拟该p*。
设置头部虚拟节点(topsite)和尾部虚拟节点(tailsite),当topsite和tailsite连通时,改模型为渗流状态。头部虚拟节点相当于水源,尾部虚拟节点相当于水桶。当水桶里有水了,说明模型处于渗流状态。
使用weighted quick-union算法解决,当然直接用迭代判断渗流也可,但算法时间复杂度高于前者
提交的percplation.zip 包含 percolation.java、percolationStats.java
percolation.java:
1 |
|
percolationStats.java:
1 | import edu.princeton.cs.algs4.StdRandom; |