mxqz 四元环计数

学术版

zhiyangfan @ 2022-01-12 08:54:02

一道题,需要三四元环计数。萌新不会四元环计数,于是乎 bdfs,然后找到一份代码。kuai 下来之后:

#include <cstdio>
#include <vector>
const int N = 2e5 + 10; std::vector<int> G[N], E[N];
std::pair<int, int> id[N]; int vis[N], a[N], b[N], c[N];
int main()
{
    int n, m; long long ans = 0; scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) scanf("%d%d", &a[i], &b[i]), ++id[a[i]].first, ++id[b[i]].first;
    for (int i = 1; i <= n; ++i) id[i].second = i;
    for (int i = 1; i <= m; ++i)
    {
        E[a[i]].push_back(b[i]); E[b[i]].push_back(a[i]);
        if (id[a[i]] > id[b[i]]) std::swap(a[i], b[i]);
        G[a[i]].push_back(b[i]);
    }
    for (int u = 1; u <= n; ++u)
    {
        for (auto v : G[u]) vis[v] = u;
        for (auto v : E[u]) for (auto w : G[v])
            if (vis[w] == u) ans += c[w]++;
        for (auto v : E[u]) for (auto w : G[v]) 
            if (vis[w] == u) c[w] = 0;
    }
    printf("%lld\n", ans); return 0;
}

但跑这个最 naive 的数据都是 0

4 4
1 2
2 3
3 4
4 1

求哪写错了


by Aestas16 @ 2022-01-12 09:09:00

你这写的难道不是三元环计数吗。。。?


by zhiyangfan @ 2022-01-12 09:11:17

@Aestas16 https://www.cnblogs.com/wzxbeliever/p/11792340.html 贺的这篇,跟三元环还是不太一样的吧。

而且三元环的数据也不对(


by Aestas16 @ 2022-01-12 09:27:42

@zhiyangfan

第 20 行和第 22 行中的

if (vis[w] == u)

显然是不对的,应改为

if (id[w] > id[u])

by zhiyangfan @ 2022-01-12 09:28:47

@Aestas16 但上面打过标记了啊


by Aestas16 @ 2022-01-12 09:28:57

你的 vis 只更新了新图上和 u 有连边的部分,枚举 w 时部分的 vis 可能是 0。


by zhiyangfan @ 2022-01-12 09:30:35

@Aestas16 草,谢谢您,我明白了,wssb


by Aestas16 @ 2022-01-12 09:33:06

@zhiyangfan 也不一定是 0,就是有的 vis[w] 访问到的是未更新过的值,然后就假掉了。


by zhiyangfan @ 2022-01-12 09:35:27

@Aestas16 总之就是 u,w 之间不一定会有之间连边,换句话说就是 id[w] > id[u] 跟存在一条 u\rightarrow w 的边不是充要条件了?qwq

不太理解四元环计数,可能问题比较nt)


by Aestas16 @ 2022-01-12 09:39:24

@zhiyangfan 是的。


by zhiyangfan @ 2022-01-12 10:13:54

@Aestas16 还有最后一个问题qwq,突然想起来的,那为啥三元环计数这样写就是对的呢


| 下一页