删边（cip）

给出一个没有重边和自环的无向图，现在要求删除其中两条边，使得图仍然保持连通。

你的任务是计算有多少组不合法的选边方案。注意方案是无序二元组。

Sol

神题，无从下手啊。

考虑点dfs建出dfs树，边分为两种--树边，非树边。

那么割断两条非树边显然不行。

考虑割一条树边a和一条非树边b，当b为a子树内唯一返祖边或a子树无返祖边时不行。

考虑两条树边ab，我们把一条返祖边打在它覆盖的所有树边上，如果这两条非树边被覆盖的集合相同，那么他们中间的那一段就会断开，就可以。

于是可以把每条返祖边给个hash值，开始处加，结束处减，统计每条边的覆盖集合，在排序统计下就行。

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 300005

#define rand() ((rand()<<15)|rand())

#define ll unsigned long long

using namespace std;

int n,m,head[maxn],tot,flag[maxn],t;

int sum[maxn],sz[maxn],a[maxn],deep[maxn];

struct node{

    int v,nex;int h;

}e[maxn*];

ll ans,ha[maxn];

void add(int t1,int t2){

    e[++tot].v=t2;e[tot].nex=head[t1];head[t1]=tot;

}

void dfs(int k,int fa){

    flag[k]=; deep[k]=deep[fa]+;

    for(int i=head[k];i;i=e[i].nex){

        if(flag[e[i].v]){

            if(e[i].v!=fa&&deep[e[i].v]<deep[k]){

                ha[e[i].v]-=e[i].h;

                ha[k]+=e[i].h;

                sz[k]++;sz[e[i].v]--;

            }

            continue;

        }

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

    }

}

void tj(int k){

    flag[k]=;

    for(int i=head[k];i;i=e[i].nex){

        if(flag[e[i].v])continue;

        tj(e[i].v);

        sz[k]+=sz[e[i].v];

        ha[k]+=ha[e[i].v];

    }

    if(k!=){

        if(!sz[k])ans+=m-,t++;

        if(sz[k]==)ans++;

    }

}

int main(){

    srand();

    cin>>n>>m;

    for(int i=,t1,t2;i<=m;i++){

        scanf("%d%d",&t1,&t2);

        add(t1,t2);add(t2,t1);

        e[tot].h=e[tot-].h=rand()*rand();

    }

    dfs(,);

    memset(flag,,sizeof flag);tj();

    sort(ha+,ha+n+);

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

        int j=i;

        for(;ha[j+]==ha[i];j++);

        if(ha[j]==)continue;

        int len=j-i+;

        ans=ans+1LL*len*(len-)/;

        i=j;

    }

    ans=ans-1LL*t*(t-)/;

    cout<<ans<<endl;

    return ;

}

巴特西

删边（cip）

删边（cip）

最新文章

热门文章