2 处理重边问题

HDU 4612

问题：

• 无向图将边双联通分量缩点后添加一条边使得割边数量变得最少,最少是多少?

  思路:

• 在2个距离最远的点添加一条边使得割边消失的最多,那么剩下的割边最少

• 先dfs一次找到距离最远的2个点中的1个.(同时记录缩点后割边的总数),

• 再一次dfs就能统计到另一个最远点的路径上的割边数量.

  技巧

1. for (int j=head[i]; j!=-1; j=edge[j].next)遍历每个点的邻接表来建立缩点后无向图(vector存)

2. e[i].vis来处理重边

   #include <iostream>
   #include <vector>
   #include <cstring>
   #include <algorithm>
   
   using namespace std;
   const int maxn = 2e5+10;
   
   struct node {
       int to,next;
       bool vis;
   } edge[maxn*10];
   vector<int> e[maxn];
   int head[maxn],h[maxn],index1;
   int low[maxn],dfn[maxn],belong[maxn],stack_[maxn];
   int top,dps,cir,n,m;
   bool in_stack[maxn];
   
   void tarjan(int x) {
       in_stack[x] = 1;
       low[x] = dfn[x] = ++dps;
       stack_[top++] = x;
       for (int i=head[x]; i+1; i=edge[i].next) {
           int to = edge[i].to;
           if (edge[i].vis) continue;
           edge[i].vis = edge[i^1].vis = 1;
           if (!dfn[to]) {
               tarjan(to);
               low[x] = min(low[x],low[to]);
           } else if (in_stack[to])
               low[x] = min(low[x],dfn[to]);
       }
       int p;
       if (low[x] == dfn[x]) {
           cir++;
           do{
               p = stack_[--top];
               in_stack[p] = 0;
               belong[p] = cir;
           }while(p != x);
       }
   }
   
   bool vis[maxn];
   int point,max_edge,ans;
   void dfs(int x,int step) {
       vis[x] = 1;
       if (step > max_edge) max_edge=step,point = x;
       for (int i=0; i<e[x].size(); ++i) {
           int to = e[x][i];
           if (!vis[to]) {
               dfs(to,step+1);
               ans++;
           }
       }
   }
   
   void add(int x,int y) {
       edge[index1].vis = 0;
       edge[index1].to = y;
       edge[index1].next = head[x];
       head[x] = index1++;
   }
   
   void init() {
       index1 = 0;
       memset(head,-1,sizeof head);
       memset(in_stack,0,sizeof in_stack);
       memset(low,0,sizeof low);
       memset(dfn,0,sizeof dfn);
       dps = top = cir = 0;
   }
   int main() {
       freopen("1.in","r",stdin);
       while (scanf("%d%d",&n,&m) && (n+m)) {
           init();
           for (int i=1; i<=m; ++i) {
               int x,y;
               scanf("%d%d",&x,&y);
               add(x,y); add(y,x);
           }
           tarjan(1);
           for (int i=1; i<=n; ++i) e[i].clear();
           for (int i=1; i<=n; ++i)
               for (int j=head[i]; j!=-1; j=edge[j].next) {
                   int to = edge[j].to;
                   if (belong[to] != belong[i]) {
                       e[belong[i]].push_back(belong[to]);
                   }
               }
           memset(vis,0,sizeof vis);
           max_edge = ans = 0;
           dfs(1,0);
           int tempans = ans;
           memset(vis,0,sizeof vis);
           max_edge = 0;
           dfs(point,0);
           cout << tempans-max_edge << endl;
       }
       return 0;
   }