三元环计数

无向图三元数计数：G - Triangle

给一个邻接矩阵表示无向边关系，求有多少个三元环？

Solution：考虑直接使用bitset优化，枚举两个点，对两个点的边表与起来，找到共同能到达的点。

时间复杂度：$O(nm/w)$(只有两个点有才会进入bitset两个序列相与)

debug:

  • 1.首先注意到对于这样的连续的不能一个一个读，不然会出问题
  • 考虑一个三元环按我们枚举的偏序关系，总共会计算三次，所以最后要除3
bitset<3001>b[3001];
void solve(){
	cin>>n;
     for(int i=1;i<=n;i++){
     	string s;cin>>s;
     	for(int j=0;j<n;j++){
     		int x=s[j]-'0';
     		b[i][j+1]=x;
     	}
     }
     int ans=0;
     for(int i=1;i<=n;i++){
     	for(int j=1;j<i;j++){
     		if(b[i][j]){
     			
     			int tmp=(b[i]&b[j]).count();
     			ans+=tmp;
     			//cerr<<i<<" "<<j<<" "<<tmp<<endl;
     		}
     	}
     }
     ans/=3;
     cout<<ans<<endl;
}

根号分治的做法不够优秀，但是思想很好，来自扶苏的题解

P1989 无向图三元环计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

个人总结：1，根据出度数和点的编号构建新图，原图中的三元环变成新图中一个三元闭合子图。

2.计算时间复杂度，以根号m为出度数分界线。度数小于mid的原点在新图中出度只会减小，大于mid的点只能给大于mid的点连边，这样的点不超过mid个。

3.每次计算的时候，给起点的所有出点标签一级出点，再给一级出点找二级出点，看有多少既是二级又是一级出点。

有向图的三元环计数

这cf题目竟然强制文件输入输出操作，不然直接wa

Solution：对于有向图,我们可以发现我们需要维护两个bitset，因为我们需要维护方向性，具体来说就是我们需要维护对于点u来说，他能到哪些点以及哪些点能到他。当发现u能到v的时候，我们需要找到k，k满足

  • k能到u
  • v能到k

我们只需要将对应类型对应点的bitset与起来就可以了

bitset<N>bei[N];
bitset<N>to[N];
void solve(){
	cin>>n;
	for(int i=0;i<n;i++){
		string s;cin>>s;
		for(int j=0;j<n;j++){
			if(s[j]=='+'){
			to[i][j]=1;bei[j][i]=1;
			}
		}
	}
	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			//有向图不存在偏序去重，只存在不同起点开始，三个起点
			if(to[i][j]){
				ans+=(to[j]&bei[i]).count();
			}
		}
	}
	ans/=3;
	cout<<ans;
}

三元环计数问题 - Tyher - 博客园 (cnblogs.com)未完待续…