题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3836
题目大意:给定一些命题,以及一部分命题的推导关系,问还需要至少添加几个推导关系能让所有的命题可以互相证明。
首先找出强连通分量,然后把每个强连通分量缩成一个点,得到一个DAG。接下来,设有a个结点(这里的结点对应于原图的一个强连通分量)的入度为0,b个结点的出度为0,则max{a,b}就是答案。注意特殊情况:当原图已经强连通时,答案是0而不是1。
引用自刘汝佳《算法竞赛入门经典 训练指南》
1 |
|