27

これは、私が答えようとしているインタビューの質問です。

メンバーを含むソーシャル ネットワークと、メンバーのペアが友情を形成した時間のタイムスタンプをN含むログ ファイルが与えられた場合M、すべてのメンバーが接続された最も早い時間を決定するアルゴリズムを設計します (つまり、すべてのメンバーは友人の友人の友人です)。 ..友人の）。ログファイルはタイムスタンプでソートされており、友情は同値関係であると仮定します。アルゴリズムの実行時間はM log Nかそれ以上で、 に比例して余分なスペースを使用する必要がありますN。

最初に思ったのは「これは無理だ！」

しかし、このソーシャル ネットワークをデータ構造として表現するにはどうすればよいかを考えました。Union-find は、使用できるデータ構造です。ここで、すべてのメンバーが接続されているとはどういう意味かを理解しなければなりません。実際のデータ構造と、すべてのメンバーが互いに友達になったときの様子を表示するにはどうすればよいですか?

システムが完全に接続される方法を視覚的または概念的に理解できるまで、そのイベントに対応するタイムスタンプを見つける方法を理解し始めることができないと思います。

4

10 に答える 10

24

union-find データ構造にフレンドシップを追加すると、2 つのグラフ コンポーネントが結合されるかどうかを確認できます。これらのマージ イベントが 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
于 2014-09-12T03:00:28.147 に答える
0

@Andrés Soto に私の意見を追加します。私は全体的に彼の答えに同意しますが、 getComponent() メソッドは必要ないと思います。

sizeWeightedUnionFind では、配列があり、2 つのコンポーネントのサイズを比較して、どちらが結合しているかを判断できるようにする必要があることを思い出してください。

    public class WeightedQuickUnionUF {
        private int[] parent;   // parent[i] = parent of i
        private int[] size;     // size[i] = number of elements in subtree rooted at i
        private int count;      // number of components

各有効なユニオンの後、サイズを更新します。したがって、更新されたサイズが N に等しいかどうかを判断するだけで済みます。そうであれば、このステップはすべての人が接続されているステップです。

于 2020-06-23T07:56:53.457 に答える