这题因为只有10组数据，输出只有YES和NO，所以就出现了各种水过的代码，好题不能就这样埋没掉啊，题解～～
这题巧妙的利用了Tarjan强连通算法low[]数组，根据仙人掌图的三个性质判断是否是仙人掌图，详细证明这里
性质1 仙人掌图的DFS树没有横向边。
性质2 Low(v)<=DFN(u) (v是u的儿子)
性质3 设某个点v有a(u)个儿子的Low值小于DFS(u)，同时u自己有b(u)条逆向边。那么a(u)+b(u)<2。
1 #include<cstdio>
2 #include<cstring>
3 using namespace std;
4 #define MIN(x,y) (x>y?y:x)
5 #define N 20005
6 #define M 50005
7
8 struct Edge{
9 int vtx,next;
10 Edge(){}
11 Edge(int v,int n):
12 vtx(v),next(n){}
13 }E[M];
14 int head[N],size;
15 int dfn[N],low[N],step,scc;
16 int stk[N],top;
17 bool ins[N],udfs[N];
18
19 void Init(){
20 memset(head,-1,sizeof(head));
21 memset(dfn,-1,sizeof(dfn));
22 memset(ins,false,sizeof(ins));
23 memset(udfs,false,sizeof(udfs));
24 size=step=scc=0; top=-1;
25 }
26
27 void Insert(int u,int v){
28 E[size]=Edge(v,head[u]);
29 head[u]=size++;
30 }
31
32 bool Tarjan(int u){
33 stk[++top]=u; ins[u]=true;
34 dfn[u]=low[u]=step++;
35 int cnt=0;
36 for(int i=head[u];i!=-1;i=E[i].next){
37 int v=E[i].vtx;
38 if(udfs[v]) return false; //udfs[]数组表示该点是否被遍历过(该点的dfs树已经被全部遍历)，如果某个点指向一个被遍历过的点，则出现横向边，返回false，性质1
39 if(dfn[v]==-1){
40 if(!Tarjan(v)) return false;
41 if(low[v]>dfn[u]) return false; //子孩子的low值大于当前点的dfn值，说明不是连通图，返回false，性质2
42 if(low[v]<dfn[u]) cnt++; //子孩子中low小于该点dfn的个数，即a(u)
43 if(cnt==2) return false; //如果a(u)+b(u)>=2 ，返回false，性质3
44 low[u]=MIN(low[u],low[v]);
45 }else if(ins[v]){
46 low[u]=MIN(low[u],dfn[v]);
47 cnt++;//该节点存在逆向边的个数，即b(u)
48 if(cnt==2) return false; //同上
49 }
50 }
51 udfs[u]=true; //该点dfs结束，标记
52 return true;
53 }
54
55 int main(){
56 int t;
57 scanf("%d",&t);
58 while(t--){
59 int n;
60 scanf("%d",&n);
61 Init();
62 while(true){
63 int u,v;
64 scanf("%d%d",&u,&v);
65 if(u==0&&v==0) break;
66 Insert(u,v);
67 }
68 bool flag=Tarjan(0);
69 if(flag){ //如果还存在没有被遍历到的点，则该图不连通，标程竟然没判断这个
70 for(int i=0;i<n;i++){
71 if(dfn[i]==-1){flag=false;break;}
72 }
73 }
74 puts(flag?"YES":"NO");
75 }
76 }