HDU 3594 Cactus（仙人掌问题）

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

题意：

一个有向图，判断是否强连通和每条边只在一个环中。

思路：

仙人掌问题。

用Tarjan算法判断强连通分量的时候，记录每节结点的父节点。当找到一个环后，回溯将该环上的所有结点+1，如果有结点出现2次了，则说明不是仙人掌了。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<vector>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<stack>

 using namespace std;

 const int maxn=+;

 int n,m;

 vector<int> G[maxn];

 int in[maxn];

 int pre[maxn],lowlink[maxn],sccno[maxn],dfs_clock,scc_cnt;

 int fa[maxn];

 int find(int u,int v)

 {

     while(fa[u]!=v)

     {

         in[u]++;

         if(in[u]>)  return ;

         u=fa[u];

     }

     return ;

 }

 int dfs(int u)

 {

     pre[u]=lowlink[u]=++dfs_clock;

     for(int i=;i<G[u].size();i++)

     {

         int v=G[u][i];

         if(!pre[v])

         {

             fa[v]=u;

             if(!dfs(v)) return ;

             lowlink[u]=min(lowlink[u],lowlink[v]);

         }

         else if(!sccno[v])

         {

             lowlink[u]=min(lowlink[u],pre[v]);

             if(!find(u,v))  return ;

         }

     }

     if(lowlink[u]==pre[u])

     {

         scc_cnt++;

         if(scc_cnt>)   return ;

     }

     return ;

 }

 int find_scc()

 {

     dfs_clock=scc_cnt=;

     memset(sccno,,sizeof(sccno));

     memset(pre,,sizeof(pre));

     memset(in,,sizeof(in));

     memset(fa,,sizeof(fa));

     for(int i=;i<n;i++)

         if(!pre[i])  if(!dfs(i))  return ;

     return ;

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<n;i++)  G[i].clear();

         while(true)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             if(u== && v==)  break;

             G[u].push_back(v);

         }

         if(find_scc() && scc_cnt==)   cout<<"YES"<<endl;

         else cout<<"NO"<<endl;

     }

     return ;

 }