51nod 1076 2条不相交的路径（边双连通分量）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1076

题意：

思路：

边双连通分量，跑一遍存储一下即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 const int mod=1e9+;

 int n, m;

 int tot;

 int head[maxn];

 int ebbc[maxn],pre[maxn],eccno[maxn],low[maxn];

 int ebbc_cnt,dfs_clock;

 stack<int> S;

 struct node

 {

     int v,next;

 }e[*maxn];

 void addEdge(int u, int v)

 {

     e[tot].v=v;

     e[tot].next=head[u];

     head[u]=tot++;

 }

 int tarjan(int u, int fa)

 {

     int lowu=pre[u]=++dfs_clock;

     S.push(u);

     for(int i=head[u];i!=-;i=e[i].next)

     {

         int v=e[i].v;

         if(!pre[v])

         {

             int lowv=tarjan(v,u);

             lowu=min(lowu,lowv);

         }

         else if(v!=fa)

             lowu=min(lowu,pre[v]);

     }

     if(pre[u]==lowu)

     {

         ebbc_cnt++;

         for(;;)

         {

             int tmp=S.top(); S.pop();

             eccno[tmp]=ebbc_cnt;

             if(tmp==u)  break;

         }

     }

     return low[u]=lowu;

 }

 void find_ebbc()

 {

     ebbc_cnt=dfs_clock=;

     memset(pre,,sizeof(pre));

     for(int i=;i<=n;i++)

     {

         if(!pre[i])  tarjan(i,-);

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d%d",&n,&m))

     {

         tot=;

         memset(head,-,sizeof(head));

         for(int i=;i<=m;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             addEdge(u,v);

             addEdge(v,u);

         }

         find_ebbc();

         int q;

         scanf("%d",&q);

         while(q--)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             if(eccno[u]==eccno[v])  puts("Yes");

             else puts("No");

         }

     }

     return ;

 }