poj 3694 Network（双连通分量）

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <vector>
  7 using namespace std;
  8 const int MAXN=100010;
  9 int bin[MAXN],n,m;
 10 int low[MAXN],dfn[MAXN],father[MAXN];
 11 int q,cut,index;
 12 vector<int>g[MAXN];
 13 
 14 int findx(int x)
 15 {
 16     return bin[x]==x?x:(bin[x]=findx(bin[x]));
 17 }
 18 int merge(int x,int y)
 19 {
 20     int fx,fy;
 21     fx=findx(x);
 22     fy=findx(y);
 23     if(fx!=fy)
 24     {
 25         bin[fx]=fy;
 26         return 1;
 27     }
 28     else
 29         return 0;
 30 }
 31 
 32 void tarjan(int i,int pre)
 33 {
 34     int j,k;
 35     low[i]=dfn[i]=++index;
 36     for (k=0; k<g[i].size(); k++)
 37     {
 38         j = g[i][k];
 39         if (!dfn[j])
 40         {
 41             tarjan(j,i);
 42             low[i]=min(low[i],low[j]);
 43             father[j]=i;
 44             if (low[j] > dfn[i])
 45                 cut++;
 46             else
 47                 merge(i,j);
 48         }
 49         else if (j!=pre)
 50         {
 51             low[i]=min(low[i],dfn[j]);
 52         }
 53     }
 54 }
 55 void lca(int u,int v)
 56 {
 57     while (u!=v)
 58     {
 59         while (dfn[u]>=dfn[v] && u!=v)
 60         {
 61             if (merge(u,father[u]))
 62                 cut--;
 63             u = father[u];
 64         }
 65         while (dfn[v]>=dfn[u]&&u!=v)
 66         {
 67             if (merge(v,father[v]))
 68                 cut--;
 69             v=father[v];
 70         }
 71     }
 72 }
 73 
 74 int main()
 75 {
 76     int i,x,y,T=1;
 77     while(~scanf("%d%d",&n,&m)&&n||m)
 78     {
 79         for(i=0; i<=n+1; i++)
 80         {
 81             g[i].clear();
 82             low[i]=dfn[i]=father[i]=0;
 83             bin[i]=i;
 84         }
 85         index=cut=0;
 86 
 87         for(i=0; i<m; i++)
 88         {
 89             scanf("%d%d",&x,&y);
 90             g[x].push_back(y);
 91             g[y].push_back(x);
 92         }
 93         tarjan(1,-1);
 94         scanf("%d",&q);
 95 
 96         printf("Case %d:
",T++);
 97         while(q--)
 98         {
 99             scanf("%d%d",&x,&y);
100             lca(x,y);
101             printf("%d
",cut);
102         }
103         cout<<endl;
104     }
105     return 0;
106 }