调试并查找算法实现

Question

问题：

我一直在尝试实现并查找算法来解决问题，但尽管添加了许多调试点，我仍然无法识别代码中的问题。

问题描述：

给定一个矩阵isConnected，其中如果第i个城市和第j个城市直接相连，则isConnected[i][j] = 1，否则isConnected[i][j] = 0，我需要找到省份总数。一个省被定义为一组直接或间接连接的城市，组外没有其他城市。

代码：

class Solution(object):
    def findCircleNum(self, m):
        n = len(m)
        parent = [i for i in range(n)]
        rank = [1 for i in range(n)]
        count = n
        for i in range(n):
            for j in range(i+1, n):
                if m[i][j] == 1:
                    p1, p2 = parent[i], parent[j]
                    if p1 != p2:
                        print(parent)
                        # print(rank)
                        count -= 1
                    r1, r2 = rank[p1], rank[p2]
                    if r1 >= r2:
                        parent[j] = p1
                        rank[p1] += 1
                    else:
                        parent[i] = p2
                        rank[p2] += 1
        return count

测试用例：

test_input = [[1,1,0,0,0,0,0,1,0,0,0,0,0,0,0],
              [1,1,0,0,0,0,0,0,0,0,0,0,0,0,0],
              [0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
              [0,0,0,1,0,1,1,0,0,0,0,0,0,0,0],
              [0,0,0,0,1,0,0,0,0,1,1,0,0,0,0],
              [0,0,0,1,0,1,0,0,0,0,1,0,0,0,0],
              [0,0,0,1,0,0,1,0,1,0,0,0,0,1,0],
              [1,0,0,0,0,0,0,1,1,0,0,0,0,0,0],
              [0,0,0,0,0,0,1,1,1,0,0,0,0,1,0],
              [0,0,0,0,1,0,0,0,0,1,0,1,0,0,1],
              [0,0,0,0,1,1,0,0,0,0,1,1,0,0,0],
              [0,0,0,0,0,0,0,0,0,1,1,1,0,0,0],
              [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
              [0,0,0,0,0,0,1,0,1,0,0,0,0,1,0],
              [0,0,0,0,0,0,0,0,0,1,0,0,0,0,1]]

print(Solution().findCircleNum(test_input))

上面的代码返回

2

但预期是

3

有人可以帮我找出代码中的问题吗？

Answer 1

有两个问题：

• 条件

  p1 != p2

  （在代码中表示

  parent[i] != parent[j]

  ）并不总是正确指示节点

  i

  和

  j

  是否位于不同的集合中。如果

  p1

  和

  p2

  通过（潜在的多个）

  parent

  依赖关系拥有共同的祖先，那么它们仍然属于同一集合。并查找中的一个重要步骤是执行find操作。有多种可能的实现方式，但这是一种：

      def find(i):
          while i != parent[i]:
              parent[i] = parent[parent[i]]
              i = parent[i]
          return i
  

  并且您应该调用它以确保到达父路径的root：

  p1, p2 = find(i), find(j)
  

• 联合操作中存在一个相关错误：

  parent[i] = p2

  可能会重新链接不是其所在树的根的节点

  i

  ，因此其祖先不会统一到另一棵树。这应该是

  parent[p1] = p2

  。在替代情况下需要类似的修正。

那么影响效率的有两点：

• 当已经发现节点位于同一集合中时，不需要执行执行并集的代码，因此您可以将其移动到

  if

  块内。

• 只有当原始两个等级相等时，等级才应该增加，因为等级代表树的高度。

这是应用了这些更正的代码（参见注释）：

class Solution(object):
    def findCircleNum(self, m):
        def find(i):  # The path-halving algorithm
            while i != parent[i]:
                parent[i] = parent[parent[i]]
                i = parent[i]
            return i

        n = len(m)
        parent = [i for i in range(n)]
        rank = [1 for i in range(n)]
        count = n
        for i in range(n):
            for j in range(i+1, n):
                if m[i][j] == 1:
                    # Need to find the roots of the trees these nodes are in:
                    p1, p2 = find(i), find(j)
                    if p1 != p2:
                        count -= 1
                        # Only need to perform union when nodes were in different sets
                        r1, r2 = rank[p1], rank[p2]
                        if r1 >= r2:
                            parent[p2] = p1  # Attach one root to the other
                            if r1 == r2:  # No increment is needed if ranks are different
                                rank[p1] += 1
                        else:
                            parent[p1] = p2  # Attach one root to the other
                            # No increment is needed if ranks are different
        return count