首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

树等价关系解决方法

2012-10-07 
树等价关系等价偶对,树的等价关系。等价类过程中MIX(s,1,2)MIX(s,3,4)MIX(s,5,6)MIX(s,7,8)S.nodes的树形态

树等价关系

  等价偶对,树的等价关系。

  等价类过程中MIX(s,1,2) MIX(s,3,4) MIX(s,5,6) MIX(s,7,8) S.nodes的树形态变化

  MIX(s,1,3) MIX(s,5,7) 再变化 MIX(s,1,5)

  上面MIX(s,i,j)这个是什么意思?

[解决办法]
这个其实是用树的形式来模拟集合的运算,运算方法如下:

1、假设集合S中有n个元素,分别记为S1,S2,...,Sn

2、每一个元素先都形成一个独立的子集合,即{S1},{S2},...,{Sn}。因为每一个子集合都是单元素的,可以看成是一个树的单独的结点。就是你写的S.nodes

3、然后具有相同的父节点的子集合会merge到一起形成一个新的集合。merge遵循的规则就是MIX(s,i,j)。这里面的s是集合,j是这个集合的结点,i是j的父节点。

MIX(s,1,2) MIX(s,3,4) MIX(s,5,6) MIX(s,7,8)

第一轮首先形成四个集合:2->1, 4->3, 6->5, 8->7, -> 指向的是父节点。

第二轮的:MIX(s,1,3) MIX(s,5,7),3的父节点是1,所以1现在有两个子节点了,2和3;7的父节点是5,所以5现在也有两个子节点了,6和7

第三轮:MIX(s,1,5), 5的父节点是1,于是1现在有3个子节点了,分别是2,3,5。这样,这七个数字就形成一个棵树了。

热点排行