学步园

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3594

题目大意：

仙人掌图的判定。

本题中的仙人掌图是一种强连通图，使得每条边至多在一个环上。

算法：

仙人掌算是一种蛮流行的图论模型吧。

wiki 上 Cactus Graph 的定义是：

一个无向连通图，任两个简单环至多含有一个公共点，等价于任一条边至多属于一个简单环，等价于任何一个块都是一个点或一个环。

但是在实际的题目和文档中，好像说是无向图的也有，说是有向图的也有。说是边至多在一个环中的也有，说是点至多在一个环中的也有。╮(╯▽╰)╭

另外我还找到了一篇介绍仙人掌图的中文文档。

文档中介绍了仙人掌图的三个性质：

性质 1: 仙人掌图的 DFS树没有横向边。
性质 2: Low[v] <= DFS[u] (v 是 u 的儿子) 
性质 3: 设某个点 u 有 a(u) 个儿子的 low 值小于 DFS[u] ，同时 u 自己有 b(u) 条反向边。那么 a(u) + b(u) < 2。

当然这道题只是要我们判定，做法是非常简单的。

直接很据仙人掌图的三个性质判定。

性质一和二都很好判定。

性质三的话，在没有横叉边的情况下，

设某个点 u 有 a(u) 个儿子的 low 值小于 DFS[u] ，同时 u 自己有 b(u) 条反向边，

那么a(u) + b(u)就等于使得low[v] < dep[u]的边(u,v)的数量（因为没横叉边的话dep[v ] < dep[u]就是反向边嘛，然后 low[v] <= dep[v]）

这代码。。全部都是 if 啊啊啊。。。

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <climits>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

const int MAXN = 21000;
vector<int> mm[MAXN];
int low[MAXN], dep[MAXN];
bool ins[MAXN];
int cot[MAXN];
bool flg;

void dfs(int u, int p)
{
    int tmp = dep[u] = low[u] = (p == -1) ? 0 : dep[p] + 1;
    ins[u] = true;
    for(int i = 0; i < mm[u].size(); i ++)
    {
        int v = mm[u][i];
        if(dep[v] != -1 && !ins[v])
        {
            flg = false;  //cactus图无横叉边
        }
        if(dep[v] == -1)
        {
            dfs(v, u);
        }
        if(low[v] > dep[u])
        {
            flg = false;  //cactus图是强联通的
        }
        if(low[v] < dep[u])
        {
            cot[u] ++;
            if(cot[u] > 1)
            {
                flg = false;  //设某个点u有a(u)个儿子的Low值小于DFS[u]，同时 u 自己有 b(u)条逆向边。那么 a(u)+b(u)<2。
            }
        }
        tmp = min(low[v], tmp);
    }
    low[u] = tmp;
    ins[u] = false;
}

int main()
{
    int cas;
    scanf("%d", &cas);
    for(int T = 1; T <= cas; T ++)
    {
        int n;
        scanf("%d", &n);
        for(int i = 0; i < n; i ++)
        {
            mm[i].clear();
        }
        memset(dep, -1, sizeof(dep));
        memset(ins, 0, sizeof(ins));
        memset(cot, 0, sizeof(cot));
        flg = true;
        int u, v;
        while(scanf("%d %d", &u, &v), u || v)
        {
            mm[u].push_back(v);
        }
        dfs(0, -1);
        for(int i = 0; i < n; i ++)
        {
            if(dep[i] == -1)
            {
                flg = false;
            }
        }
        if(flg)
        {
            puts("YES");
        }
        else
        {
            puts("NO");
        }
    }
    return 0;
}