先抛出一个问题：给一个有向图，问从\(1\)节点出发，求每个节点的受支配集。这里，支配的定义为：若从\(1\)结点出发到\(v\)节点的所有路径中，都必须经过\(u\)节点，则称\(u\)支配\(v\)。那么受支配集意思就是对于\(v\)点满足条件的\(u\)点的集合。那么根据支配的定义，我们可以

支配在有向图G中，存在源点s，若从s出发的到达点y的路径都经过点x,称x支配y。注意：若源点s有多个，则可以虚拟一个起点性质1.源点s支配所有的点，点x一定支配x本身性质2.支配的传递性，若x支配y,y支配z,则x支配z性质3.若x支配y,y支配x,则有x=y性质4.若x支配z,y也支配z,则x和y之间一定

P5180【模板】支配树来咯，我们来说说一般图上的支配树。（前排提醒：本文实质是对老师讲的内容的补充，阅读本文前应该知道\(\operatorname{idom}\)及其在DAG上的求解方法，具体可以去查看ZJOI2012灾难的题解。）常见的做法是Languaer-Tarjan算法，该算法的核心在于提出了半支配点