poj3177Redundant Paths【构造双连通分量：并查集缩点 模板】

Description

Input

Output

Sample Input

7 7
1 2
2 3
3 4
2 5
4 5
5 6
5 7

Sample Output

2

这个题就是问加几条边可以构成双连通分量，一开始图样图森破的以为只是求桥的个数就好，然而并非如此……

构造双连通分量的加边数=（原图的叶节点数+1）/2    因为双连通分量需要成环嘛，原图已经是连着的了，所以只需要在另一侧再加一条边就成环啦~怎么判断哪里是叶结点呢？先用并查集缩点，把所有当前的双连通分量都缩到一起，然后就构成了只有桥的图，枚举每个桥，记录每个点的次数，每次加一。只有1的点就是原图的叶结点~。~

而且并查集不就是干这个用的么╮(╯_╰)╭

/***************
poj3177
2015.11.20
***************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>

using namespace std;

const int N=5006;
vector<int>G[N];
struct bridge
{
    int u,v;
}bg[2*N];
int vis[N],low[N],dfn[N],Time;
int fa[N],deg[N];
int n,m,cnt;
void init()
{
    for(int i=0;i<n;i++) G[i].clear();
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(deg,0,sizeof(deg));
    for(int i=1;i<=n;i++) fa[i]=i;
    cnt=Time=0;
}
int findset(int x)
{
    if(x!=fa[x])
        fa[x]=findset(fa[x]);
    return fa[x];
}
void Tarjan(int u,int father)
{
    low[u] = dfn[u] = ++Time;
    vis[u] = 1;
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(v == father)
            continue;
        if(!vis[v])
        {
            Tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(low[v] > dfn[u])        //u->v为桥
                bg[cnt].u = u,bg[cnt++].v = v;
            else   //否则，u,v同属一个连通分量，合并
            {
                int fx = findset(u);
                int fy = findset(v);
                if(fx != fy)
                    fa[fx] = fy;
            }
        }
        else
            low[u] = min(low[u],dfn[v]);
    }
}

int main()
{
   // freopen("cin.txt","r",stdin);
    while(~scanf("%d%d", &n, &m))
    {
        init();
        for(int i=0;i<m;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        Tarjan(1,-1);
        for(int i=0;i<cnt;i++)
        {
            int fx=findset(bg[i].u);
            int fy=findset(bg[i].v);
            deg[fx]++;
            deg[fy]++;
        }
        int leaf=0;
        for(int i=1;i<=n;i++)
            if(deg[i]==1)
                leaf++;
        printf("%d\n",(leaf+1)/2);
    }
    return 0;

}