这东西其实就是一种暴力,只不过巧妙的是每一个环恰好统计了一次。
三元环计数推荐一篇博客,,很详细,很清楚。 每一个三元环之所以被算了一次,是因为一个三元环在新图上必定只有一个点的出度为2,然后我们只在这个点上更新三元环数量。 然后我放了个代码:#define forE(i, x, y) for(int i = head[x], y; (y = e[i].to) && ~i; i = e[i].nxt)In bool dcmp(int x, int y) {return d[x] == d[y] ? x > y : d[x] > d[y];}In void calc_3(){ for(int x = 1; x <= n; ++x) { forE(i, x, y) if(dcmp(x, y)) ++cnt[y]; forE(i, x, y) if(dcmp(x, y)) forE(j, y, z) if(dcmp(y, z) && cnt[z]) ++cir3[x], ++cir3[y], ++cir3[z]; forE(i, x, y) if(dcmp(x, y)) cnt[y] = 0; }}四元环计数网上好想找不到,抄了神仙的代码自己脑补了一下。 还是将图按上述规则转化成有向无环图,然后对于每一个点\(x\),遍历他在新图上的出边,即走到的点为\(y\),再遍历\(y\)在原图和\(y\)相邻的点\(z\),然后用上面代码的dcmp函数判断\(x, z\),如果成立,说明找到了四元环的一半,那么用\(z\)上已经记录的“半个”四元环个数更新\(x, y, z\),然后在\(z\)上记录这又多了一个“半个”四元环。 但这样会导致先找到的“半个”四元环没有和后面的“半个”四元环匹配上,因此我们还要按上述方法再遍历一遍\(x, y, z\),同时更新每一个节点上的四元环数量。 按这种方法遍历一定会保证每一个四元环只被算过一次,但证明我还是没太想明白。
In void calc_4(){ for(int x = 1; x <= n; ++x) { forE(i, x, y) if(dcmp(x, y)) forE(j, y, z) if(dcmp(x, z)) { int& v = cnt[z]; cir4[x] += v, cir4[y] += v, cir4[z] += v; ++v; } forE(i, x, y) if(dcmp(x, y)) forE(j, y, z) if(dcmp(x, z)) cir4[y] += (--cnt[z]); }}