我已经有 N 个节点和 N-1 条边,基本上是无向无环 MST。我想基本上计算不相交的节点集的数量。如果两个节点具有相同的父节点并且节点的度数相同,则它们属于集合。例如。在给定的树中。{3,4} 属于同一个集合,因为parent[3]=1
andparent[4]=1
和degree[3]=degree[4]=1 ;
{5} 和 {2} 也形成不相交的集合,因为 parent[2]=parent[5]=1 但是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/
请有人说出可以执行的断续集的数量