hiho一下第178周《Stable Members》题目分析

3
0

《Stable Members》题目分析

本题是一道比较复杂的图论题目。

我们可以把这个学习小组的网络看成一个DAG(有向无环图)。对于每个节点X,如果从X到master(0号节点)的所有路径都包含节点Y,我们就称Y 是X的支配点。(注意我们不把0号节点认为是X的支配点) 如果X没有支配点,那么X就是stable的;如果有大于0个支配点,那么X就是unstable的。

比较容易看出X的支配点(如果存在)一定是一条链。换句话说,假设Y1, Y2是两个不同的X的支配点,那么或者Y1是Y2的支配点,或者Y2是Y1的 支配点。

定理一:X是stable的当且仅当1)X直接与0相连;2)存在两条不相交的路径X-...-Y与X-...-Z且Y和Z都是stable的。

对于一个unstable的节点X,X一定存在唯一的stable的支配节点,记为SD(X)。唯一性的证明可以利用反正法结合定理一得到。

最后我们来分析一个节点X究竟是不是stable的,事实上X的性质可以通过分析X的前驱节点得到。

  1. 如果X有两个或两个以上stable的前驱节点,那么根据定理一,X一定是stable的。
  2. 如果X恰好有一个stable的前驱节点,不妨设为Y。

1) 如果X只有Y一个前驱节点,那么显然Y是X的支配点,X是unstable的。
2) 如果X还有其他前驱节点,那么对于任意unstable的前驱节点U,如果SD(U)都等于Y,则Y是X的支配点,X是unstable的,并且有SD(X)=Y。>否则只要存在一个U满足SD(U)不等于Y,那么X-Y和X-U-...-SD(U)一定是两条不相交的路径,并且Y和SD(U)都是stable的。根据定理一X是stab le的。
3. 如果X没有stable的前驱节点。同样是考虑任意unstable的前驱节点U,如果SD(U)都相等,那么这个相等的SD(U)就是X的支配点,于是X是unstable的,并且有SD(X)=SD(U)。否则只要有2个节点U1U2使得SD(U1)!=SD(U2),那么X-U1-...-SD(U1),与X-U2-...-SD(U2)根据定理一可知X是stable的。

于是最终的算法是将整个DAG拓扑排序。首先与0之间相连的点都标记为stable,并且SD值就是本身节点。之后根据拓扑序依次判断每个节点是 否stable,如果unstable则求出SD值。

0 answer(s)

write answer 切换为英文 切换为中文


转发分享