[关闭]
@xzyxzy 2018-07-02T10:14:15.000000Z 字数 240 阅读 555

三元环计数

图论

作业部落

评论地址


求解无向图中三个点构成的环的个数

将边定向,由度数小的点指向大的,相同则指向编号大的
枚举每条边,将所有与相连的点打上标记,再枚举与相连的点,如果有标记则算进答案

复杂度是

因为每个点的出度不超过
证明:对于度数小于的点显然,度数大于的点出度一定指向度数大于的点,而度数大于的点不超过个,所以每个点的出度都小于等于

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注