algorithm - Union-find 表示为社交网络

Question

这是我要回答的面试问题:

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 M log N or better and use extra space proportional to N.

我首先想到的是......“我做不到!”。

但是转念一想，这个社交网络怎么用数据结构来表达。 Union-find是一个可以使用的数据结构。现在我必须明白当所有成员都连接时意味着什么。如何查看实际的数据结构以及每个成员彼此成为 friend 时的样子？

我认为只有在我能够从视觉上或概念上理解系统如何完全连接之前，我才能开始弄清楚如何找到与该事件对应的时间戳。

Answer 1

当您将友谊添加到 union-find 数据结构时，您可以注意它是否会导致两个图形组件被连接。只需不断添加边，直到发生 N-1 个合并事件。

伪代码形式:

G := UnionFind(1..N)
count := 0
for timestamp, p1, p2 in friendships {
    if G.Find(p1) != G.Find(p2) {
        G.Union(p1, p2)
        count++
        if count == N-1 {
            return timestamp
        }
    }
}
return +infinity