Cactus

240 11 22 02 33 20 040 11 22 33 01 30 0 Sample Output
YESNO 
题目大意：
                 仙人掌图：连通图中没有一条边属于两个环
                 求是否是仙人掌图
题目思路：
                首先考虑连通性我们可以用targan判断，然后targan中遇到环就dfs遍历环，给每条边计数，如果边出现次数大于1就说明该边出现于两个环中
AC代码：
#include<cstring>#include<cstdio>const int maxn = 2e4+10;const int maxm = 5e4+10;struct st{    int v,nex;}edge[maxm];int hed[maxn],vis[maxn],belon[maxn],in[maxn];int low[maxn],dfn[maxn],stack[maxn],fa[maxn];int n,e,cnt,num,top,ok;void add(int u,int v){    edge[e].v=v,edge[e].nex=hed[u],hed[u]=e++;}void dfs(int u,int v){   //遍历环    while(fa[u]!=v){        in[u]++;        if(in[u]>1){            ok=0;            return ;        }        u=fa[u];    }}void targan(int u){      //targan判断是否联通    if(!ok)return ;    low[u]=dfn[u]=++num;    stack[top++]=u;    vis[u]=1;    for(int i=hed[u];~i;i=edge[i].nex){        int v = edge[i].v;        if(!dfn[v]){            fa[v]=u;            targan(v);            if(low[v]<low[u])low[u]=low[v];        }else if(vis[v]&&dfn[v]<low[u]){            dfs(u,v);            if(!ok)return ;            low[u]=dfn[v];        }    }    if(dfn[u]==low[u]){        cnt++;        if(cnt>1){            ok=0;            return ;        }        int x ;        do{            x=stack[--top];            belon[x]=cnt;            vis[x]=0;        }while(x!=u);    }}void init(){    memset(dfn,0,sizeof(dfn));    memset(hed,-1,sizeof(hed));    memset(vis,0,sizeof(vis));    memset(in,0,sizeof(in));    e=1;    cnt=top=num=0;}int main(){    int t;scanf("%d",&t);    while(t--){        init();        scanf("%d",&n);        int u,v;        ok=1;        while(scanf("%d%d",&u,&v),u+v){                u++,v++;            for(int i=hed[u];~i;i=edge[i].nex){                if(edge[i].v==v)ok=0;            }            add(u,v);        }        for(int i=1;i<=n&&ok;i++){            if(!dfn[i])targan(i);        }        if(ok)printf("YES/n");        else printf("NO/n");    }    return 0;}