HDU3594 Cactus （[好题] 强连通之仙人掌图 ）

题意：判断是不是仙人掌图，仙人掌图的定义，
1.首先是强连通的
2.任意一个遍只能属于一个圈。
仙人掌图的分析

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<vector>
#include<cstdlib>
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define cl(a,b) memset(a,b,sizeof(a));
#define LL long long
#define P pair<int,int>
#define X first
#define Y second
#define pb push_back
#define fread(zcc)  freopen(zcc,"r",stdin)
#define fwrite(zcc) freopen(zcc,"w",stdout)
using namespace std;
const int maxn=20005;
const int inf=999999;
vector<int> G[maxn];
int low[maxn],dfn[maxn],s[maxn],belong[maxn];
bool ins[maxn];
int num,cnt,top;
bool ok;
bool vis[maxn];
void dfs(int u){
    low[u]=dfn[u]=++num;
    ins[u]=true;
    s[top++]=u;
    int N=G[u].size();
    int sum=0;
    for(int i=0;i<N;i++){
        int v=G[u][i];
        if(vis[v])ok=false;//性质1
        if(!dfn[v]){
            dfs(v);
            if(low[v]>dfn[u])ok=false;//性质2
            if(low[v]<dfn[u])sum++;
            if(sum==2)ok=false;
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]){
            low[u]=min(dfn[v],low[u]);
            sum++;
            if(sum==2)ok=false;//性质3
        }
    }
    if(low[u]==dfn[u]){
        int v=-1;
        cnt++;
        while(u!=v){
            v=s[--top];
            ins[v]=false;
            belong[v]=cnt;
        }
    }
    vis[u]=true;
}
void Tarjan(int n){
    cl(dfn,0);
    cl(ins,false);
    cl(belong,0);
    cl(vis,false);
    ok=true;
    num=top=cnt=0;
    for(int i=1;i<=n;i++){
        if(!dfn[i])dfs(i);
    }
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n;
        scanf("%d",&n);
        for(int i=0;i<=n;i++){
            G[i].clear();
        }
        int x,y;
        while(scanf("%d%d",&x,&y)&&(x+y)){
            x++;y++;
            G[x].pb(y);
        }
        Tarjan(n);
        printf("%s\n",cnt==1&&ok?"YES":"NO");
    }
    return 0;
}