1

我在计算每个不相交的集合成员中的元素数量时遇到了一些麻烦。例如，如果有人输入：

注意：第一个数字 = 源顶点，第二个数字 = 目标顶点，第三个数字 = 长度

0 2 1

4 8 7

5 8 6

1 2 5

2 3 17

我将 2 作为集合的计数

4 8 7

5 8 6

和 3 作为集合的计数，因为两者都由 2 个和 3 个（各自的）元素连接。

0 2 1

1 2 5

2 3 17

我的想法是将每个不相交集的元素数存储到一个整数数组中，这样我就可以访问永远不相交集的计数。下面是我查找元素并将它们合并到同一个集合中的实现。我还有一个函数可以在每个集合中找到根。

int node::findSet(int v, int *parent)
{
  if(parent[v] < 0)
    return v;
  else
  {
    return parent[v] = findSet(parent[v], parent);
  }
}

void node::joinSets(int c, int p1, int p2, int *parents)
{
  join(findSet(p1,parents),findSet(p2,parents),parents);
}

void node::join(int p1, int p2, int *parents)
{
  if(parents[p2] < parents[p1])
    parents[p1] = p2;
  else
  {
    if(parents[p1] == parents[p2])
      parents[p1]--;
    parents[p2] = p1;
  }
}

我只是不确定在哪里/何时增加和维护我的计数器。任何帮助，将不胜感激。谢谢！

4

1 回答 1

3

如果要计算连接每个不相交集的边数，请将每个根的当前大小存储在类似于 的数组中parents。

当边缘出现时，找到两个节点的根。如果它们相等，则增加根的计数器（我假设没有重复的边）。如果不是，则合并根，并为生成的根的计数器值将根的计数器值的总和加一。

于 2012-11-13T11:01:04.417 回答