mxqz 四元环计数
  • 板块学术版
  • 楼主zhiyangfanshotacon
  • 当前回复12
  • 已保存回复12
  • 发布时间2022/1/12 08:54
  • 上次更新2023/10/28 12:29:46
查看原帖
mxqz 四元环计数
137603
zhiyangfanshotacon楼主2022/1/12 08:54

一道题,需要三四元环计数。萌新不会四元环计数,于是乎 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 的数据都是 00

4 4
1 2
2 3
3 4
4 1

求哪写错了

2022/1/12 08:54
加载中...