HDU3594-仙人掌图

一时失言乱红尘 2022-07-16 16:18 131阅读 0赞

# Cactus #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 1934    Accepted Submission(s): 891**

Problem Description

1. It is a Strongly Connected graph.  
2. Each edge of the graph belongs to a circle and only belongs to one circle.  
We call this graph as CACTUS.  
  
![C306-1002-1.jpg][]  
  
There is an example as the figure above. The left one is a cactus, but the right one isn’t. Because the edge (0, 1) in the right graph belongs to two circles as (0, 1, 3) and (0, 1, 2, 3).

Input

The input consists of several test cases. The first line contains an integer T (1<=T<=10), representing the number of test cases.  
For each case, the first line contains a integer n (1<=n<=20000), representing the number of points.  
The following lines, each line has two numbers a and b, representing a single-way edge (a->b). Each case ends with (0 0).  
Notice: The total number of edges does not exceed 50000.

Output

For each case, output a line contains “YES” or “NO”, representing whether this graph is a cactus or not.

Sample Input

2
    4
    0 1
    1 2
    2 0
    2 3
    3 2
    0 0
    4
    0 1
    1 2
    2 3
    3 0
    1 3
    0 0

Sample Output

YES
    NO

**题目大意：**

仙人掌图：连通图中没有一条边属于两个环

求是否是仙人掌图

**题目思路**：

首先考虑连通性我们可以用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;
    }

[C306-1002-1.jpg]: /images/20220709/c157ecf71144454a869ba36647b0f3d3.png