题意简述
给定一张无向图,若图中三个点 $a$,$b$,$c$ 满足 $a$ 与 $b$ 有边相连,$a$ 与 $c$ 有边相连,$b$ 与 $c$ 有边相连,则称点 $a$,$b$,$c$ 构成了一个三角形,求在给定的图中三角形的个数。
题目分析
一个比较直接的想法是枚举 $a$,$b$,$c$ 的编号,时间复杂度为 $O(n^3)$,无法通过本题。
我们可以只枚举 $a$,$b$ 的编号,若一个点与 $a$ 有边相连且与 $b$ 有边相连,则这个点必定是满足条件的点 $c$。使用 bitset
可以比较方便地解决这个问题。
Code
#include<bits/stdc++.h>
using namespace std;
long long n,ans;
bitset<3005> m[3005];
char t;
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>t;
if(t=='1') m[i][j]=1;
else m[i][j]=0;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(m[i][j]){
ans+=(long long)((m[i]&m[j]).count());//满足条件的c点个数
}
}
}
cout<<ans/6<<endl;//统计出的结果有一定的重复,需要除以6后再输出
return 0;
}