学步园

题目链接

/*
 *题目大意：
 *要求最少添加多少条边可变无桥的连通图;
 *
 *算法分析：
 *求割点和桥可以用tarjan算法,对图进行dfs,记录每个点的第一次到达时间dfn[i];
 *并记录一个low[i]表示该点及其子孙结点所能到达的dfn最小的点;
 *这个到达并不是普通意义的到达,而是在遍历过程中;
 *通过非树枝边(一定是返祖边,因为是无向图,没有横叉边)能够直接到达的点,而不是连续使用返祖边能到达的;
 *这样就可以把low总结为low[u]=min(low[v](v为u的儿子结点),dfn[v](v是u通过返祖边能到达的点),dfn(u));
 *然后我们可以粗略地认为返祖边可以连同树枝边共同构成一个环;
 *对于边的双连通,环一定是双连通的(一定不是桥),不在环内的边一定是桥;
 *对于点的双连通,如果一个点在环内,且是该环与外界的直接连接点,那么它一定是割点,环内其余点不是割点,不在环内的一定是割点;
 *对于边的双连通,若边(u,v),dfn[u]<low[v](即不在环内)则为桥;
 *对于点的双连通,若dfn[u]<=dfn[v](小于是不在环内的点,等于是环与外界的唯一连接点),
 *或者u为根且u有多个子树(说明u不在环内,因为没有横叉边)则为割点;
 *
 *对于边双连通分支,在求出所有的桥以后,把桥边删除;
 *原图变成了多个连通块,则每个连通块就是一个边双连通分支;
 *桥不属于任何一个边双连通分支,其余的边和每个顶点都属于且只属于一个边双连通分支;
 *
 *一个有桥的连通图,通过加边变成边双连通图的方法为:
 *首先求出所有的桥,然后删除这些桥边,剩下的每个连通块都是一个双连通子图;
 *把每个双连通子图收缩为一个顶点,再把桥边加回来,最后的这个图一定是一棵树,边连通度为1;
 *统计出树中度为1的节点的个数,即为叶节点的个数,记为leaf;
 *则至少在树上添加(leaf+1)/2条边,就能使树达到边双连通,所以至少添加的边数就是(leaf+1)/2;
 *具体方法为,首先把两个最近公共祖先最远的两个叶节点之间连接一条边;
 *这样可以把这两个点到祖先的路径上所有点收缩到一起,因为一个形成的环一定是双连通的;
 *然后再找两个最近公共祖先最远的两个叶节点,这样一对一对找完,恰好是(leaf+1)/2次,把所有点收缩到了一起;
**/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;

const int N=5555;

struct edge
{
    int to;
    int next;
};

edge G[N];
int head[N];
int n,m,idx,cnt;
int low[N],visit[N],degree[N];
bool map[N][N];

void Addedge(int u,int v)
{
    G[idx].to=v;
    G[idx].next=head[u];
    head[u]=idx++;
}

void dfs(int x, int p)
{
    visit[x]=true;
    low[x]=cnt++;
    for(int i=head[x]; i!=-1; i=G[i].next)
    {
        int j=G[i].to;
        if(j==p)
            continue;
        if(!visit[j])
            dfs(j,x);
        low[x]=min(low[x],low[j]);
    }
}
int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
    while(~scanf("%d%d",&n,&m))
    {
        memset(head,-1,sizeof(head));
        memset(visit,0,sizeof(visit));
        memset(map,0,sizeof(map));

        idx=cnt=0;
        int u,v;
        while(m--)
        {
            scanf("%d%d",&u,&v);
            if(!map[u][v])
            {
                map[u][v]=map[v][u]=true;
                Addedge(u,v);
                Addedge(v,u);
            }
        }

        dfs(1,1);
        for(int i=1; i<=n; i++)
        {
            for(int u=head[i]; u!=-1; u=G[u].next)
            {
                int j=G[u].to;
                if(low[i]!=low[j])
                    degree[low[i]]++;
            }
        }

        int res=0;
        for(int i=0; i<=n; i++)
        {
            if(degree[i]==1)
            {
                res++;
            }
        }
        printf("%d\n",(res+1)>>1);
    }
    return 0;
}