BZOJ1718分离的路径

边双题。

求的就是最少加几条边可以使一个图变成边双联通图。

首先tarjan求一下边双，缩完点变成一颗树，统计度数为1的点（无根树的叶子），把这个数算出来，设为x，则ans=（x+1）/2。

这个可以怎么理解呢？先分一下类，当x为偶数时，想让叶子节点边双联通就好像接到一条边，使之在一个环上（简单环肯定边双应该没问题吧），那么，我们任选两个叶子，将他们接到lca上就可以了，切路径上任意一条边都可以，自己画图看看吧，证明不好证，显然还是挺显然的，总共x/2。

当x为奇数时，把x-1个节点如上处理，剩下一个，肯定要加一条边把他接上去，总共（x+1）/2。

然后根据向下取整，简写为（x+1）/2。

得出结论，使一棵树变成边双的额外边数为（叶子节点数+1）/2。

#include<iostream>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<cstdio>

#include<vector>

#include<queue>

#include<stack>

#include<set>

#include<map>

using namespace std;

int read(){

    int sum=,f=;char x=getchar();

    while(x<''||x>''){

        if(x=='-') f=-;

        x=getchar();

    }while(x>=''&&x<=''){

        sum=sum*+x-'';

        x=getchar();

    }return sum*f;

}

struct EDGE{

    int ed,nex;

}edge[],edgec[];int first[],firstc[],numc=,num=;

int n,m;

int dfn[],low[],bl[],du[];

int edcc,ord,ans;

bool bridge[];

void add(int st,int ed){

    edge[++num].ed=ed;

    edge[num].nex=first[st];

    first[st]=num;

}

void addc(int st,int ed){

    edgec[++numc].ed=ed;

    edgec[numc].nex=firstc[st];

    firstc[st]=numc;

}

void tarjan(int x,int in_edge){

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

    for(int i=first[x];i;i=edge[i].nex){

        int y=edge[i].ed;

        if(!dfn[y]){

            tarjan(y,i);

            low[x]=min(low[x],low[y]);

            if(low[y]>dfn[x])

                bridge[i]=bridge[i^]=true;

        }else if(i!=(in_edge^))

            low[x]=min(low[x],dfn[y]);

    }

}

void dfs(int x){

    bl[x]=edcc;

    for(int i=first[x];i;i=edge[i].nex){

        int y=edge[i].ed;

        if(bl[y]||bridge[i]) continue;

        dfs(y);

    }

}

int main(){

    //freopen("b.in","r",stdin);

    n=read();m=read();

    for(int i=,x,y;i<=m;i++){

        x=read();y=read();

        add(x,y);add(y,x);

    }

    for(int i=;i<=n;i++)

        if(!dfn[i]) tarjan(i,);//求桥

    for(int i=;i<=n;i++)

        if(!bl[i]){

            edcc++;

            dfs(i);

        }

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

        int x=edge[i].ed,y=edge[i^].ed;

    //    cout<<"x="<<x<<" y="<<y<<" bl[x]=";

    //    cout<<bl[x]<<" bl[y]="<<bl[y]<<endl;

        if(bl[x]==bl[y]) continue;

        addc(bl[x],bl[y]);

        du[bl[x]]++;

    }

    for(int i=;i<=edcc;i++)

        if(du[i]==) ans++;

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

    return ;

}

巴特西

BZOJ1718分离的路径

最新文章

热门文章