连通专题：双连通分量加边->强连通

题目链接：http://poj.org/problem?id=3177
题目大意：有n个牧场，Bessie 要从一个牧场到另一个牧场，要求至少要有2条独立的路可以走。现已有m条路，求至少要新建多少条路，使得任何两个牧场之间至少有两条独立的路。两条独立的路是指：没有公共边的路，但可以经过同一个中间顶点。

就是给你一个无向图，问你至少加多少条边能变成双连通图

分析：对图进行缩点，形成一棵树，树上度为1的点。必须向其他节点连边，才能使得这两个点和他们LCA上所有的点连通。所以肯定是度为1的节点向度为1的节点连边。这样一次消去两条度为1的点。

强连通： max(r(1), c(1));	r(1)入度为1的节点数  c(1)出度为1的节点数
双连通：（n+1）/2；      		n：度为1的节点数

具体做法：首先把两个最近公共祖先最远的两个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2次，把所有点收缩到了一起。

错误做法：认为每一个双连通分量内的点low[]值都是相同的。多个环的时候是错误的。

样例：
5 6
1 2
2 3
3 4
4 2
4 5
5 1

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1010;
struct Node
{
    int to;
    int next; //起点相同的上一条边下标
    bool cut; //边是否为桥
}edge[maxn*2];

int cut;      //边数

int head[maxn];//点i的最后一条边

int dfn[maxn];
int low[maxn];
int tot;
int bvis[maxn];//点属于哪个边连通分量
int N;         //连通分量数

vector<int> BCC[maxn];

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

//e是为了去重,e是边在数组的位置
//另一种去重为DFS(u,fa),v!=fa,但是有重边时可能会判断错误
//比如没重边时,假设(a,b)是桥,但是如果(a,b)有重边,那么(a,b)就不是桥了
void Tarjan(int u, int e)//求出所有的桥
{
    cout<<"P:"<<u<<endl;
    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]);
            cout<<u<<' '<<low[u]<<' '<<v<<' '<<low[v]<<endl;

            if(low[v]>dfn[u])//桥
            {
                cout<<"hhh"<<endl;
                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;
    BCC[N].push_back(u);
    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);
        }
    }
}

int main()
{
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        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);
            }
        }

        for(int i=1;i<=n;i++)
        {
            //cout<<dfn[i]<<' '<<low[i]<<endl;
        }

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

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

    return 0;
}