连通专题 点连通分量+树的直径

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4612
题目大意：n个点由m条无向边连接，求加一条边后桥的最少数量，有重边，并且重边不算桥。

思路：tarjan算法求出所有的桥，得到一颗生成树，我们再加一条边必然成环，要使得桥的数量最少，就得使得这个环中的边最多。于是找这棵树距离根最远的两条链(深度最大)。连接起来。答案就是n-1-D1-D2

好像这个思路没有问题。实际上是有问题的。例如：

3， 6， 9深度都一样。但答案显然是9和3或者9和6不是3 6。因为两条最长的链可能共用节点。所以正确的思路应该是n-1-直径。

而且这个模板对重边适用。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int maxm=1e6+10;
struct Node
{
    int to;
    int next; //起点相同的上一条边下标
    bool cut; //边是否为桥
}edge[maxm*2];//双向边开两倍空间

int cut;      //边数
int ans=0;
int head[maxn];//点i的最后一条边
int dfn[maxn];
int low[maxn];
int tot;
int bvis[maxn];//点属于哪个边连通分量
int N;         //连通分量数

void addEdge(int u, int v)
{
    edge[cut].to=v;
    edge[cut].next=head[u];
    edge[cut].cut=0;
    head[u]=cut++;
}

void Tarjan(int u, int e)//求出所有的桥
{
    low[u]=dfn[u]=++tot;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(i==(e^1))//这里只会去重该边的反边,不会去它的重边(所以模板对重边适用,不被计算成桥)
        {
            continue;
        }
        if(dfn[v]==0)
        {
            Tarjan(v, i);
            low[u]=min(low[u], low[v]);

            if(low[v]>dfn[u])//桥
            {
                ans++;
                edge[i].cut=1;
                edge[i^1].cut=1;
            }
        }
        else if(dfn[v]<dfn[u])
        {
            low[u]=min(low[u], dfn[v]);
        }
    }
}

void dfs(int u)//求出每个点所在的边连通分量
{
    dfn[u]=1;
    bvis[u]=N;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        if(edge[i].cut)
        {
            continue;
        }
        if(dfn[edge[i].to]==0)
        {
            dfs(edge[i].to);
        }
    }
}

vector<int> e[maxn];
int d, k;
int vis[maxn];
void DFS(int u, int s)
{
    vis[u]=1;
    if(s>d)
    {
        k=u, d=s;
    }
    for(int i=0;i<e[u].size();i++)
    {
        int v=e[u][i];
        if(!vis[v])
        {
            DFS(v, s+1);
        }
    }
}
int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m),m*n)
    {
        ans=0;
        for(int i=0;i<maxn;i++)
        {
            e[i].clear();
        }
        memset(head, -1, sizeof(head));

        cut=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&a,&b);
            addEdge(a, b);
            addEdge(b, a);
        }

        memset(dfn, 0, sizeof(dfn));
        memset(bvis, 0, sizeof(bvis));
        tot=N=0;
        for(int i=1;i<=n;i++)
        {
            if(dfn[i]==0)
            {
                Tarjan(i, -1);
            }
        }

        memset(dfn, 0, sizeof(dfn));

        for(int i=1;i<=n;i++)
        {
            if(dfn[i]==0)
            {
                N++;
                dfs(i);
            }
        }

        for(int u=1;u<=n;u++)
        {
            for(int i=head[u];i!=-1;i=edge[i].next)
            {
                int v=edge[i].to;
                if(bvis[u]!=bvis[v])
                {
                    e[bvis[u]].push_back(bvis[v]);
                    e[bvis[v]].push_back(bvis[u]);
                }
            }
        }
        memset(vis, 0, sizeof(vis));
        d=k=0;
        DFS(1, 0);
        memset(vis, 0, sizeof(vis));
        DFS(k ,0);
        cout<<ans-d<<endl;
    }

    return 0;
}