1

タプルのリストが表示されます。(i,j)各タプル(i,j)はそれを示しi、j友達です。友情は伝染性であるため、タプルが存在しない場合でも、とがi友達jであり、jとkが友達でiあり、友達である場合。したがって、問題は、1からNまでの整数のセット、およびタプルのリストについて、すべての数値が互いに友達であるかどうかを効率的に判断する方法です。k(i,k)

素朴なアルゴを除いて、グラフを使用せずにこれを行うための効率的なアルゴを考案することは可能ですか？

この質問の別の変形があります。ここで、質問は、特定のタプル(m,n)が友達であるかどうかを見つけることです。これは、スタックを使用して実装できます。

4

1 に答える 1

2

私は、壁を取り除いて迷路を作るアルゴリズムを学びました。

int friendGroups[N];

// initially, all numbers are in a "forever alone" group.
for(i = 0; i < N; i++) {
    friendGroups[i] = i;
}

int findFriendGroup(int p) {
    int g = friendGroups[p];
    if (g != p) {
        g = friendGroups[p] = findFriendGroup(g);
    }
    return g;
}
void addFriendship(int i, int j) {
    friendGroup[findFriendGroup(i)] = findFriendGroup(j);
}
int areFriends(int i, int j) {
    return (findFriendGroup(i) == findFriendGroup(j));
}

findFriendGroup()潜在的に非効率的に見えますが、各呼び出しは漸近的に O(A^(-1)(N)) のコストがかかります。ここで、A^(-1) は逆アッカーマン関数であり、O(1) に非常に近いため、心配する必要はありません。

int singleFriendGroup() {
    int g = findFriendGroup(0);
    int i;

    for(i = 1; i < N; i++) {
        if (findFriendGroup(i) != g) {
            return 0;
        }
    }
    return 1;
}

各人は、他の人または自分自身を「指し示し」ます。各フレンド グループには、自分自身を指し示すプライマリ メンバーがいます ( friendGroups[i] == i)。 findFriendGroup()ポイントのチェーンをたどってグループの主要メンバーを見つけ、その途中でチェーン内の各人を直接主要メンバーに向けさせます。2 つのグループを統合するには ( addFriendship())、1 つのグループのプライマリ メンバが別のグループのプライマリ メンバを指すようにします。

于 2012-10-28T22:26:22.077 に答える