algorithm - 不使用图形可能有任何有效的解决方案吗？

Question

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

除了朴素算法之外，是否有可能设计出一种高效的算法来在不使用图形的情况下做到这一点？

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

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;
}

每个人都“指向”另一个人或他自己。每个 friend 组都有一个指向自己的主要成员 (friendGroups[i] == i)。 findFriendGroup() 按照点链找到组的主要成员，并在返回的过程中使链中的每个人都直接指向主要成员。要统一两个组 (addFriendship())，使一个组的主要成员指向另一个组的主要成员。