三元环、四元环计数

这东西其实就是一种暴力，只不过巧妙的是每一个环恰好统计了一次。

三元环计数推荐一篇博客，【科技】三元环计数，很详细，很清楚。
每一个三元环之所以被算了一次，是因为一个三元环在新图上必定只有一个点的出度为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]);
	}
}

三元环、四元环计数

相关推荐