[学习笔记]无向图三元环计数

考虑每次枚举一个环起点,即考虑是否枚举\((i,j),(j,k)\)是否有\((i,k)\)成立。

考虑对其重新编号,对其按度数偏序连边。

考虑其大于\(\sqrt n\)的不多于\(\sqrt n\)个。

我们每次操作的时候实际上是对一个点枚举的复杂度为其出度乘入度。

知其为\(O(n\sqrt n)\)

无向图三元环计数
#include<bits/stdc++.h>
#define N 300005

int n,m;

int u[N],v[N],in[N],vis[N],ans = 0;

std::vector<int>e[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;++i)
	scanf("%d%d",&u[i],&v[i]),in[u[i]] ++ ,in[v[i]] ++ ;
	for(int i = 1;i <= m;++i){
		if((in[u[i]] == in[v[i]]) ? u[i] > v[i] : in[u[i]] > in[v[i]])
		std::swap(u[i],v[i]);
		e[u[i]].push_back(v[i]);
	}
	for(int i = 1;i <= n;++i){
		for(auto j : e[i])vis[j] = 1;
		for(auto j : e[i])
		for(auto k : e[j])
		if(vis[k])
		ans ++ ;
		for(auto j : e[i])
		vis[j] = 0;
	}
	std::cout<<ans<<std::endl;
}

上一篇:素数的判断方法


下一篇:关于二次分块这么一个奇奇怪怪的东西