HDU3594 Cactus 强连通判断一条边是否只在一个环内

题意很简单，如果图满足

1：强连通图

2：图中每条边只处于一个环内

怎么样判断一个边只在一个环内呢？其实在没有找到一个环之前的时候，有一个DFS的过程，在这个过程中每走到一个点，我们就记录一下它是有哪一个点走下来的也就是这个点的上一层的点，等到我们找到环的时候，我们马上返回去查找，查找那个点是 out了两次以上，那么肯定有边处于两个或者两个以上环内，就不符合了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; typedef struct Node{ int from,to; int nex; int value; }; Node edge[20000 * 500]; int head[20000 + 10],low[20000 + 10],dfn[20000 + 10],id[20000 + 10],Stack[20000 + 10],out[20000 + 10]; bool vis[20000 + 10]; int father[20000 + 10]; int vis_num,scc_num,tot,stack_num,tot2; bool flag; int min(int a,int b) { if(a
                    
                      1) { flag = true; return ; } v = father[v]; } } void tarjan(int v) { dfn[v] = low[v] = ++vis_num; vis[v] = true; Stack[stack_num++] = v; for(int i=head[v];i!=-1;i=edge[i].nex) { int u = edge[i].to; if(dfn[u] == -1) { father[u] = v;//记录上一个点是哪个点 tarjan(u); low[v] = min(low[u],low[v]); } else if(vis[u]) { low[v] = min(dfn[u],low[v]); find(u,v);//遇到环了 马上返回去进行查找 } } int tmp; if(low[v] == dfn[v]) { scc_num++; do { tmp = Stack[--stack_num]; id[tmp] = scc_num; vis[tmp] = false; }while(tmp != v); } if(scc_num > 1) { flag = true; return; } } void cal(int n) { for(int i=1;i<=n;i++) { if(dfn[i] == -1) tarjan(i); if(flag) break; } } int main() { int t,n; scanf("%d",&t); while(t--) { clear(); scanf("%d",&n); int a,b; while(true) { scanf("%d %d",&a,&b); if(a == 0 && b == 0) break; addedge(a + 1,b + 1); } cal(n); if(flag) puts("NO"); else puts("YES"); } return EXIT_SUCCESS; }

HDU3594 Cactus 强连通 判断一条边是否只在一个环内