【HDU4612】双连通分量求桥

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4612

题目大意：给你一个无向图，问你加一条边后最少还剩下多少多少割边。

解题思路：好水的一道模板题。先缩点变成一颗树，再求树的最长直径，直径两端连一条边就是最优解了。

但是....我WA了一个下午.....没有处理重边。

重边的正确处理方法：只标记已经走过的正反边，而不限制已走过的点。换句话说就是可以经过重边再次走向父亲节点，而不能经过走过边的反向边返回父亲节点。

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <queue>
  5 #include <algorithm>
  6 #include <cstring>
  7 using namespace std;
  8 
  9 const int maxn=222222;
 10 const int maxm=2222222;
 11 int  dfn[maxn], low[maxn], head[maxn], stack[maxn], instack[maxn], belong[maxn];
 12 int  reach[maxm], next[maxm], sign[maxm];
 13 int  visit[maxn];
 14 int  top, Index, scnt, edge, pos, bridgenum;
 15 int  n, m;
 16 pair<int,int>num[maxm];
 17 
 18 struct node
 19 {
 20     int u;
 21     int dis;
 22     int fa;
 23 };
 24 queue<node>q;
 25 
 26 void init()
 27 {
 28     memset(head,-1,sizeof(head));
 29     memset(dfn,0,sizeof(dfn));
 30     memset(instack,0,sizeof(instack));
 31     Index=top=edge=scnt=bridgenum=0;
 32 }
 33 
 34 void addedge(int u, int v)
 35 {
 36     sign[edge]=0, reach[edge]=v, next[edge]=head[u], head[u]=edge++;
 37     sign[edge]=0, reach[edge]=u, next[edge]=head[v], head[v]=edge++;
 38 }
 39 
 40 void tarjan(int u)
 41 {
 42     stack[++top]=u;
 43     dfn[u]=low[u]=++Index;
 44     instack[u]=1;
 45     for(int i=head[u]; i>=0; i=next[i])
 46     {
 47         if(sign[i]) continue;
 48         sign[i]=1, sign[i^1]=1;  ///处理重边，只标记边，而不限制点
 49         int v=reach[i];
 50         if(!dfn[v])
 51         {
 52             tarjan(v), low[u]=min(low[u],low[v]);
 53             if(dfn[u]<low[v]) bridgenum++;  ///求桥的数量
 54         }
 55         else if(instack[v]) low[u]=min(low[u],dfn[v]);
 56     }
 57     if(low[u]==dfn[u])
 58     {
 59         int v;
 60         scnt++;   ///双连通分量的数量
 61         do
 62         {
 63             v=stack[top--];
 64             instack[v]=0;
 65             belong[v]=scnt;
 66         }
 67         while(u!=v);
 68     }
 69 }
 70 
 71 int bfs(int st)
 72 {
 73     int maxx=0;
 74     while(!q.empty()) q.pop();
 75     memset(visit,0,sizeof(visit));
 76     node s, p;
 77     s.u=st, s.dis=0, s.fa=-1;
 78     q.push(s);
 79     visit[s.u]=1;
 80     while(!q.empty())
 81     {
 82         p=q.front();
 83         q.pop();
 84         for(int i=head[p.u]; i>=0; i=next[i])
 85         {
 86             int v=reach[i];
 87             if(v==p.fa) continue;
 88             s.u=v, s.dis=p.dis+1, s.fa=p.u;
 89             if(!visit[s.u])
 90             {
 91                 visit[s.u]=1, q.push(s);
 92                 if(s.dis>maxx)
 93                 {
 94                     maxx=s.dis;
 95                     pos=s.u;
 96                 }
 97             }
 98         }
 99     }
100     return maxx;
101 }
102 
103 void Solve()
104 {
105     memset(head,-1,sizeof(head));
106     edge=0;
107     for(int i=1; i<=m; i++)
108     {
109         int u=num[i].first, v=num[i].second;
110         int x=belong[u], y=belong[v];
111         if(x!=y) addedge(x,y);
112     }
113     bfs(1);
114     int ans=bfs(pos);
115     cout << bridgenum-ans <<endl;
116 }
117 
118 int main()
119 {
120     while(cin >> n >> m, n+m)
121     {
122         init();
123         for(int i=1; i<=m; i++)
124         {
125             int u, v;
126             scanf("%d%d",&u,&v);
127             num[i].first=u, num[i].second=v;
128             addedge(u,v);
129         }
130         for(int i=1; i<=n; i++)
131             if(!dfn[i]) tarjan(i);
132         Solve();
133     }
134     return 0;
135 }
136 
137 /*
138 10 11
139 1 2
140 2 3
141 3 4
142 2 4
143 3 6
144 5 10
145 5 7
146 7 8
147 8 9
148 7 9
149 3 5
150 */

View Code

【HDU4612】 双连通分量求桥

【HDU4612】双连通分量求桥