《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值。