1

互いに素な各セットメンバーの要素数を数えるのに少し問題があります。たとえば、誰かが次のように入力した場合：

注：最初の数値=ソース頂点、2番目の数値=宛先頂点、3番目の数値=長さ

0 2 1

4 8 7

5 8 6

1 2 5

2 3 17

セットのカウントとして2があります

4 8 7

5 8 6

両方が2つと3つの（それぞれの）要素によって接続されているため、セットのカウントとして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ます。

エッジが来たら、両方のノードのルートを見つけます。それらが等しい場合は、ルートのカウンターをインクリメントします (繰り返しエッジがないと仮定しています)。そうでない場合は、ルートを結合し、結果のルートのカウンター値に、ルートのカウンター値の合計に 1 を加えます。

于 2012-11-13T11:01:04.417 に答える