algorithm - 在不使用图表的情况下有任何有效的解决方案吗？

Question

给出了一个元组列表(i,j)，每个元组都(i,j)告诉你i并且j是朋友。友谊是具有传染性的，所以如果i和j是朋友，j并且k是朋友，i并且k是朋友，即使元组(i,k)不存在。所以问题是，对于一组从 1 到 N 的整数，以及一个元组列表，如何有效地确定所有数字之间是否是朋友。

除了天真的算法，是否有可能在不使用图表的情况下设计一种有效的算法来做到这一点？

这个问题还有另一个变体，问题是找出给定的元组是否(m,n)是朋友。这可以使用堆栈来实现。

Answer 1

我已经学会了一种通过移除非常适用的墙壁来制作迷宫的算法。

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()沿着点链找到组的主要成员，并在返回的路上使链中的每个人直接指向主要成员。要统一两个组 ( addFriendship())，使一个组的主要成员指向另一组的主要成员。