题目大意：给定一个无向图，有N个节点（N<=25000）、M条边（M <=50000），没有重边。给Q（Q<=50000）个询问，每次询问输入两个节点，问是否存在两条从一个节点到另一个节点互不相交（不经过同一条边）的路径。

分析：

　　边双连通图：如果一个无向连通图中去掉任意一条边，不改变图的连通性，或者说，对图中任意两个点，都存在两条互不相交的路径，都则称为边双连通图。

　　题目即求询问的两个点是否在同一个边双连通分量中。用Tarjan算法。

　　Tarjan算法大致原理就是从一个节点开始做dfs，用两个数组dfn和low记录结点被搜到的时间和结点所在边双连通分量的最小根结点。将正在搜索的结点入栈，如果搜到某个点u时，u的祖先v在栈内，且存在一条还未走过的边(u,v)，则说明u,v属于同一个边双连通分量，low[u]=min(low[x],dfn[to]).若u的孩子还未访问过，则继续访问，并更新low[u]=min(low[u],low[v]).如果low[v]>dfn[u],说明v的孩子不能到达u的祖先，则边(u,v)是一条桥.去掉图中所有的桥后，连通分量即为边双连通分量.每个结点和每条边最多只访问一次，故复杂度为O(N+M).

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 const int N=25005,M=50005; 8 int n,m,Q,s[M],t[M],p[N],start,aim,Instack[N],dfn[N],low[N],have[M],had[N],cnt=0,Delete[M]; 9 vector
          
            G[N];10 stack
           
             sta;11 int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);}12 void dfs(int x){13 had[x]=1;14 low[x]=dfn[x]=cnt++;15 Instack[x]=1;16 for(int i=0;i
            
             dfn[x])Delete[e]=1;29 }30 Instack[x]=0;31 }32 void Tarjan(int x){33 if(had[x])return;34 memset(Instack,0,sizeof(Instack));35 memset(have,0,sizeof(have));36 while(!sta.empty())sta.pop();37 dfs(x);38 }39 int main(){40 // freopen("e:\\in.txt","r",stdin);41 // freopen("e:\\out.txt","w",stdout);42 cin>>n>>m;43 int a,b;44 memset(had,0,sizeof(had));45 memset(Delete,0,sizeof(Delete));46 for(int i=0;i
             
              >a>>b;48 G[--a].push_back(i);49 G[--b].push_back(i);50 s[i]=a;t[i]=b;51 }52 for(int i=0;i
              
               >Q;61 while(Q--){62 cin>>start>>aim;63 if(Find(--start)==Find(--aim))cout<<"Yes\n";64 else cout<<"No\n";65 }66 return 0;67 }