HDU 3594 Cactus （仙人掌图、Tarjan）

HDU 3594 Cactus （仙人掌图、Tarjan）

Description

Input

The input consists of several test cases. The first line contains an integer T (1<=T<=10), representing the number of test cases.For each case, the first line contains a integer n (1<=n<=20000), representing the number of points.The following lines, each line has two numbers a and b, representing a single-way edge (a->b). Each case ends with (0 0).Notice: The total number of edges does not exceed 50000.

Output

For each case, output a line contains “YES” or “NO”, representing whether this graph is a cactus or not.

Sample Input

240 11 22 02 33 20 040 11 22 33 01 30 0

Sample Output

YESNO

题意

给出一张有向图，判断其是否是仙人掌图。

思路

在解决这道题之前我们首先要知道什么是仙人掌图。

直观的说，仙人掌图就是一个一个的圈直接“粘”在一起的图，圈之间没有公共边。

我们主要根据其以下三点性质来做出判断：

仙人掌图的 DFS 树没有横向边​​Low(u)<=DFN(v)​​ （u 是 v 的儿子）设某个点 v 有 a(v) 个儿子的 Low 值小于 DFN(v) ，同时 v 自己有 b(v) 条逆向边，那么​​a(v)+b(v)<2​​

而 ​​LOW​​​ 与 ​​DFN​​​ 之前我们所学习的 ​​Tarjan​​ 算法中已经遇到了，直接拿来改改就可以了。

AC 代码

#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。