HDU 4612 Warm up(Bridges + Diameter of tree)

Description

N个点M条无向边(可含重边)，再添加一条边，最后的桥最少有多少？

Analyze

本来想当成POJ 3694 处理，桥的数目 - (距离LCA和最大的两个叶子节点到LCA的距离和)，但两层循环求到LCA距离和会TLE！

学到了：树的直径dist[ BFS( BFS(1) ) ]

第一次BFS返回一个叶子节点

Code

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200005;
const int M = 4200005;

int n, m, Q;
int cnt, tot, idx, id[N], h1[N], h2[N], low[N], times[N], num_bridges;

bool bridge[M];
struct edge
{
    int u, v, pre;
} e[M];

void init()
{
    cnt = tot = idx = num_bridges = 0;
    memset(h1, -1, sizeof(h1));
    memset(h2, -1, sizeof(h2));
    memset(id,  0, sizeof(id));
    memset(low, 0, sizeof(low));
    memset(times, 0, sizeof(times));
    memset(bridge, 0, sizeof(bridge));
}

void add(int u, int v, int head[])
{
    e[cnt].u = u;
    e[cnt].v = v;
    e[cnt].pre = head[u];
    head[u] = cnt++;
}

void Tarjan(int x, int pre_e_num)///Get all bridges!
{
    low[x] = times[x] = ++tot;
    for(int i = h1[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(i == (pre_e_num ^ 1))///Deal with repeated edges!
            continue;
        if(!times[to])
        {
            Tarjan(to, i);
            low[x] = min(low[x], low[to]);
            if(low[to] > times[x])
            {
                num_bridges++;
                bridge[i] = bridge[i ^ 1] = 1;
            }
        }
        else
            low[x] = min(low[x], times[to]);
    }
}

void DFS(int x)///Shrink by bridges!
{
    id[x] = idx;
    for(int i = h1[x]; ~i; i = e[i].pre)
    {
        int to = e[i].v;
        if(id[to] || bridge[i])///Don't go through any bridge!
            continue;
        DFS(to);
    }
}

bool vis[N];
int dist[N];

int BFS(int x)
{
    memset(vis, 0 ,sizeof(vis));
    queue<int> q;
    q.push(x);
    vis[x] = 1, dist[x] = 0;
    int now;
    while(!q.empty())
    {
        now = q.front();
        q.pop();
        for(int i = h2[now]; ~i; i = e[i].pre)
        {
            int to = e[i].v;
            if(vis[to])
                continue;
            dist[to] = dist[now] + 1;
            q.push(to);
            vis[to] = 1;
        }
    }
    return now;
}

int main()
{
    while(~scanf("%d %d", &n, &m) && (n + m))
    {
        init();
        int u, v;
        for(int i = 0; i < m; ++i)
        {
            scanf("%d %d", &u, &v);
            add(u, v, h1), add(v, u, h1);
        }

        Tarjan(1, -1);

        for(int i = 1; i <= n; ++i)
            if(!id[i])
                ++idx, DFS(i);

        int number = cnt;
        for(int i = 0; i < number; i += 2)
        {
            u = e[i].u, v = e[i].v;
            if(id[u] == id[v])
                continue;
            bridge[cnt] = 1;
            add(id[u], id[v], h2);
            bridge[cnt] = 1;
            add(id[v], id[u], h2);
        }

        int diameter = dist[BFS(BFS(1))];
        cout << num_bridges - diameter << '\n';
    }
    return 0;
}