【BZOJ】1718: [Usaco2006 Jan] Redundant Paths 分离的路径

【题意】给定无向连通图，要求添加最少的边使全图变成边双连通分量。

【算法】Tarjan缩点

【题解】首先边双缩点，得到一棵树（无向无环图）。

入度为1的点就是叶子，两个LCA为根的叶子间合并最高效，直接将两个叶子并入双连通分量后建新图。

若没有两个LCA为根的叶子则往下换根。

ans=(num+1)/2。

猜想：如果要统计方案的话，就每次并后再次缩点，找一个非叶子作为根。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=,maxm=;

struct edge{int u,v,from;}e[maxm];

int first[maxn],n,m,tot=,col[maxn],dfn[maxn],low[maxn],cnt,in[maxn],ans;

bool iscut[maxm];

void insert(int u,int v){tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}

void tarjan(int x,int fa){

    dfn[x]=low[x]=++cnt;

    for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){

        if(!dfn[e[i].v]){

            tarjan(e[i].v,x);

            low[x]=min(low[x],low[e[i].v]);

            if(low[e[i].v]>dfn[x])iscut[i]=iscut[i^]=;

        }

        else low[x]=min(low[x],dfn[e[i].v]);

    }

}

void dfs(int x,int k){

    col[x]=k;

    for(int i=first[x];i;i=e[i].from)if(!iscut[i]&&!col[e[i].v]){

        dfs(e[i].v,k);

    }

}

int main(){

    scanf("%d%d",&n,&m);

    int u,v;

    for(int i=;i<=m;i++){

        scanf("%d%d",&u,&v);

        insert(u,v);insert(v,u);

    }

    tarjan(,);

    cnt=;

    for(int i=;i<=n;i++)if(!col[i])dfs(i,++cnt);

    for(int i=;i<=tot;i+=)if(col[e[i].u]!=col[e[i].v])in[col[e[i].u]]++,in[col[e[i].v]]++;

    ans=;

    for(int i=;i<=cnt;i++)if(in[i]==)ans++;

    printf("%d",(ans+)/);

    return ;

}