c++ - 计算不相交集合中的成员数

Question

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

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

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

我只是不确定何时何地增加和维护我的计数器。任何帮助，将不胜感激。谢谢!

Answer 1

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

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