【HDU 3594 Cactus】tarjan+仙人掌图

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3594

题目大意：给你一个图，让你判断他是不是仙人掌图。

仙人掌图的条件是：

1、是强连通图。

2、每条边在仙人掌图中只属于一个强连通分量。

仙人掌图介绍 --> https://files.cnblogs.com/ambition/cactus_solution.pdf

解题思路：

1、首先得先熟练掌握塔尖tarjan算法的应用。

2、必须了解仙人掌图的三个性质：

（1）.仙人掌dfs图中不能有横向边，简单的理解为每个点只能出现在一个强联通分量中。

（2）.low[v]<dfn[u],其中u为v的父节点

（3）.a[u]+b[u]<2 ， a[u]为u节点的儿子节点中有a[u]个low值小于u的dfn值。b[u]为u的逆向边条数。

三个性质有一个不满足则不是仙人掌图。

 1 #include <algorithm>
 2 #include <vector>
 3 #include <iostream>
 4 #include <cstdio>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 const int maxn=20005;
 9 int  dfn[maxn], low[maxn], stack[maxn], belong[maxn];
10 bool instack[maxn], color[maxn], ok;
11 int top, scnt, Index, n;
12 vector<int>vt[maxn];
13 
14 void Init_tarjan()
15 {
16     top=scnt=Index=0;
17     for(int i=1; i<=n; i++) dfn[i]=low[i]=instack[i]=color[i]=0;
18 }
19 
20 void tarjan(int u)
21 {
22     stack[++top]=u;
23     dfn[u]=low[u]=++Index;
24     instack[u]=1;
25     int cnt=0;
26     for(int i=0; i<vt[u].size(); i++)
27     {
28         int v=vt[u][i];
29         if(color[v]) ok=false; ///!!!性质1
30         if(!dfn[v])
31         {
32             tarjan(v);
33             if(low[v]>dfn[u]) ok=false; ///!!!性质2
34             if(low[v]<dfn[u]) cnt++;
35             if(cnt==2) ok=false;
36             low[u]=min(low[u],low[v]);
37         }
38         else if(instack[v])
39         {
40             low[u]=min(low[u],dfn[v]);  ///这里把时间戳dfn写成了low，错误了好几次
41             cnt++;
42             if(cnt==2) ok=false;   ///!!!性质3
43         }
44     }
45     if(low[u]==dfn[u]) ///有向图缩点
46     {
47         int v;
48         scnt++; ///强连通分量的个数
49         do
50         {
51             v=stack[top--];
52             instack[v]=0;
53             belong[v]=scnt;///！让一个强连通分量缩成一个点
54         }while(u!=v);
55     }
56     color[u]=1;
57 }
58 
59 int main()
60 {
61     int  T, u, v;
62     cin >> T;
63     while(T--)
64     {
65       for(int i=0; i<maxn; i++)
66         vt[i].clear();
67       cin >> n;
68       while(1)
69       {
70          scanf("%d%d",&u,&v);
71          if(u+v==0) break;
72          vt[u+1].push_back(v+1);
73       }
74       Init_tarjan();
75       ok=true;
76       for(int i=1; i<=n; i++)
77         if(!dfn[i]) tarjan(i);
78       printf((scnt==1&&ok==true)?"YES\n":"NO\n");
79     }
80 }