一道题,需要三四元环计数。萌新不会四元环计数,于是乎 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
求哪写错了