hdu3594 强连通（仙人掌图）

题意：给定一张有向图，问是否是仙人掌图。仙人掌图的定义是，首先，这张图是一个强连通分量，其次所有边在且仅在一个环内。

首先，tarjan可以判强连通分量是否只有一个。然后对于所有边是否仅在一个环内，我的做法是，当一个点在 tarjan 的 dfs 中，引出下一条边，如果这条边指向了一个时间轴上比它大的点，那么该点一定是 dfs 树中它的后继节点，在之前必定有一条这两点之间的路径，那么这两点之间就已经有两条路径了，而从后继节点一定能返回到祖先节点而形成环（强连通），所以返回祖先节点的路径一定与两点间的两条路径形成两个环，就不符合仙人掌图了。而如果这条边指向了一个时间轴上比它小的点，那么或者那个点是这个圈的访问祖先，或者那个点是其他圈中的点，那么这一段一定都在一个圈上，那就不断遍历回祖先将点的访问数+1。最后再判断是否每个点的访问数小于等于1就行了。

 #include<stdio.h>

 #include<string.h>

 #include<stack>

 #include<queue>

 using namespace std;

 const int maxn=2e4+;

 const int maxm=5e4+;

 int head[maxn],point[maxm],nxt[maxm],size;

 int n,t,scccnt;

 int stx[maxn],low[maxn],scc[maxn];

 int fa[maxn];

 int vis[maxn];

 stack<int>S;

 bool f;

 void init(){

     memset(head,-,sizeof(head));

     size=;

     f=;

     memset(vis,,sizeof(vis));

     memset(fa,-,sizeof(fa));

 }

 void add(int a,int b){

     point[size]=b;

     nxt[size]=head[a];

     head[a]=size++;

 }

 void dfs(int s,int pre){

     fa[s]=pre;

     stx[s]=low[s]=++t;

     S.push(s);

     for(int i=head[s];~i;i=nxt[i]){

         int j=point[i];

         if(!stx[j]){

             dfs(j,s);

             low[s]=min(low[s],low[j]);

         }

         else if(!scc[j]){

             if(stx[j]<stx[s]){

                 int k=s;

                 while(k!=j&&k!=-){

                     vis[k]++;

                     k=fa[k];

                 }

             }

             else f=;

             low[s]=min(low[s],stx[j]);

         }

     }

     if(low[s]==stx[s]){

         scccnt++;

         while(){

             int u=S.top();S.pop();

             scc[u]=scccnt;

             if(s==u)break;

         }

     }

 }

 void setscc(){

     memset(stx,,sizeof(stx));

     memset(scc,,sizeof(scc));

     t=scccnt=;

     for(int i=;i<n;++i)if(!stx[i])dfs(i,-);

 }

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         int m;

         scanf("%d",&n);

         init();

         int a,b;

         while(scanf("%d%d",&a,&b)&&a+b){

             add(a,b);

         }

         setscc();

         for(int i=;i<n;++i)if(vis[i]>)f=;

         if(scccnt>||!f)printf("NO\n");

         else printf("YES\n");

     }

     return ;

 }