私はNノードとN-1エッジで、基本的に無向非循環MSTでした。基本的に、ばらばらなノードのセットの数を数えたいと思います。2 つのノードが同じ親を持ち、ノードの次数が同じ場合、2 つのノードはセットに属します。たとえば。指定されたツリーで。{3,4} は同じセットに属します。なぜならparent[3]=1、 andparent[4]=1およびdegree[3]=degree[4]=1 ; {5} と {2} も非素集合 を形成するからdegree[5]=2 and degree[2]=3です。素集合の総数を数えなければなりません。私は次のような構造でやろうとしています:
`define MAX 100000
int set;
struct parent
{
int z[MAX-1];
}
p_data[MAX];
`
しかし、p_data配列が非常に大きいことを示しています。ですから、助けてください。上記で定義された素集合の総数を数えるには、どのようなデータ構造またはロジックに従う必要がありますか。
ここに画像を投稿できません: この画像を参照してください: http://postimage.org/image/sw2nrciib/
実行できるディスジョイントセットの数を誰か教えてください