首页 > 代码库 > 竞赛图如何构造三元环

竞赛图如何构造三元环

讲解视频

一场NOIp模拟赛的T3里看到的一个东西,因为那道题目不开放评测,所以简单写一下。

 

假设存在这样一张竞赛图,其中存在这样一个环

$node_a \rightarrow node_b \rightarrow node_c \rightarrow node_d \rightarrow node_e \rightarrow node_a$

 

首先明确,这是一个竞赛图,对于任意的$node_a$和$node_b$,要么存在$node_a \rightarrow node_b$要么存在$node_b \rightarrow node_a$。

 

我们的目标是在一个竞赛图中构造三元环,根据这个方法,我们就可以使用$Tarjan$算法把任意大小的环构造成三元环。

 

一些具体的步骤

定义环的大小为$tol$,那么上述的环$tol=5$,目标是把$tol$变为3,一个方法是在环中找到一个$tol=3$的环,一个方法是不断删点,最终删到$tol=3$

 

我们同时进行这两个方法。

再回到上面的性质:

对于任意的$node_a$和$node_b$,要么存在$node_a \rightarrow node_b$要么存在$node_b \rightarrow node_a$

首先对于$node_a \rightarrow node_b \rightarrow node_c$

必定存在$node_a \rightarrow node_c$或者 $node_c \rightarrow node_a$

 

对于第一个,我们可以将$tol--$,对于第二个,显然找到了一个$tol=3$的环,

然后继续执行下去就行了。

 

竞赛图如何构造三元环