menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[三元环计数]HDU6184【Counting Stars】题解
apps HDU
local_offer 查看标签
comment 0 条评论

题目概述

给出一张无向图,求 $4$ 个点构成两个有公共边的三元环的方案数。

解题报告

填坑填坑,如果我们知道每条边所在的三元环个数 $num_i$ ,那么 $\sum_{i=1}^{m}{num_i\choose 2}$ 就是答案。

问题是怎么求三元环个数,朴素暴力肯定不行,但是很明显我们可以对度数进行阈值优化,就可以把复杂度降到 $O(m\sqrt m)$ 了,不过这样常数巨大(度数总和是 $2m$ )。

还有种比较好的方法:给无向边定向,从度数小的连向度数大的(度数相同看编号),然后每次枚举一条边,枚举这条边两个端点出去的点,如果有相同的点就找到了三元环。由于是从度数小的连向度数大的点,所以不会有环(即每个三元环只统计到一遍),并且每个点的出度不超过 $\sqrt m$ ,复杂度也是 $O(m\sqrt m)$ ,但是常数小。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=200000;

int n,m,X[maxm+5],Y[maxm+5],d[maxn+5],pt[maxn+5],ti,vis[maxn+5],num[maxm+5];
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5],w[maxm+5];LL ans;

#define Add(x,y,z) (son[++E]=(y),w[E]=(z),nxt[E]=lnk[x],lnk[x]=E)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    while (~scanf("%d%d",&n,&m)){
        E=0;for (int i=1;i<=n;i++) lnk[i]=0,d[i]=0;
        for (int i=1;i<=m;i++) scanf("%d%d",&X[i],&Y[i]),d[X[i]]++,d[Y[i]]++,num[i]=0;
        for (int i=1;i<=m;i++) d[X[i]]>d[Y[i]]||d[X[i]]==d[Y[i]]&&X[i]>Y[i]?Add(Y[i],X[i],i):Add(X[i],Y[i],i);
        for (int i=1;i<=m;i++){
            ti++;for (int j=lnk[X[i]];j;j=nxt[j]) pt[son[j]]=w[j],vis[son[j]]=ti;
            for (int j=lnk[Y[i]];j;j=nxt[j]) if (vis[son[j]]==ti) num[w[j]]++,num[pt[son[j]]]++,num[i]++;
        }ans=0;for (int i=1;i<=m;i++) ans+=(LL)num[i]*(num[i]-1)>>1;printf("%lld\n",ans);
    }return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up