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 的数据都是
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] 跟存在一条
不太理解四元环计数,可能问题比较nt)
by Aestas16 @ 2022-01-12 09:39:24
@zhiyangfan 是的。
by zhiyangfan @ 2022-01-12 10:13:54
@Aestas16 还有最后一个问题qwq,突然想起来的,那为啥三元环计数这样写就是对的呢