理解
时间复杂度 \(O(M \sqrt{M})\)
作用
求出无向图的所有三元环
过程
首先要对所有的无向边进行定向，对于任何一条边，从度数大的点连向度数小的点，如果度数相同，从编号小的点连向编号大的点。
此时这张图是一个有向无环图。
- 枚举每一个点u，然后将u的所有相邻的点都标记上“被u访问了”，
- 然后再枚举u的相邻的点v，
- 然后再枚举v的相邻的点w，
如果w存在“被u访问了”的标记，那么(u,v,w)就是一个三元环了，且每个三元环只会被计算一次。
这样为什么是对的呢？
按照算法的流程，原来图中的一个三元环 \(((i,j,k)\) 在重定向之后一定变成了 i 向 j,k 连边，j,k 之间再连一条边的情况,不妨设为\(j \to k\) 。
我们枚举 i 时会标记 j,k ，再遍历 j找第三个点的时候一定会找到 k 。
并且对于这个环，遍历顺序只可能是 \(i\to j \to k\)，也就是我们只能由 i 来找到这个环。每个点我们只会枚举一次，
所以图中的每一个三元环，我们都会遍历 且 仅遍历一次。
那么时间复杂度为什么 \(O(m\sqrt m)\) 呢？
考虑每条边 \((u,v)\) 对时间复杂度的贡献与 \(v\) 的出度同阶，总的时间复杂度应当是 $\sum_{i=1}^m d_v$，这里 \(d\) 是出度。
对于原图中度数不大于 \(\sqrt{m}\) 的点，新图中的度数也不可能更大，所以上界 \(\sqrt{m}\)。
对于原图中度数大于 \(\sqrt{m}\) 的点，由于我们只向度数大的点连边，而度数大于 \(\sqrt{m}\) 的点最多有 \(\sqrt{m}\)个，度数也不可能超过 \(\sqrt m\)。
综上，总的时间复杂度 \(O(m\sqrt{m})\)。
模板代码
时间复杂度 \(O(M \sqrt{M})\)
模板题
注意及时剪枝结束，不然会超时。
代码
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define int short int
const int N=3010;
const int maxn=3010;
int vis[maxn];
typedef vector< vector<int> > Graph;
Graph G;
int n, u, v;
int m=0;
int getnum(){
memset(vis,0,sizeof vis);
for(int i = 1; i <= n; ++i) {
for(int j : G[i])
if(G[i].size() > G[j].size() || G[i].size() == G[j].size() && i > j) vis[j] = i;
for(int j : G[i])
if(G[i].size() > G[j].size() || G[i].size() == G[j].size() && i > j)
for(int k : G[j])
if(G[j].size() > G[k].size() || G[j].size() == G[k].size() && j > k)
if(vis[k] == i)
return 1;
}
return 0;
}
void solve(){
m=0;
cin>>n;
G.resize(n + 1);
for(int i = 1; i <= n; ++i) {
G[i].clear();
}
// cout<<G[1].size()<<endl;
// cout<<G[1][2]<<endl;
for(int i=1;i<=n-1;i++){
for(int j=i+1;j<=n;j++){
int t;cin>>t;
if(t){
int u=i,v=j;
m++;
G[u].push_back(v);
G[v].push_back(u);
}
}
}
// cout<<m<<endl;
if(m>2e4) {
cout<<"Bad Team!"<<endl;
return ;
}
int ans1 = 0,ans2=0;
ans1=getnum();
m=n*(n-1)/2-m;
if(m>2e4) {
cout<<"Bad Team!"<<endl;
return ;
}
for(int i = 1; i <= n; ++i) {
memset(vis,0,sizeof vis);
for(int j : G[i])
{
vis[j]=1;
}
G[i].clear();
for(int j=1;j<=n;j++){
if(vis[j]==0) G[i].push_back(j);
}
}
ans2=getnum();
if(ans1==0 && ans2==0) cout<<"Great Team!"<<endl;
else cout<<"Bad Team!"<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) solve();
return 0;
}
原文1：https://blog.51cto.com/u_15072778/3772333
原文2：https://www.luogu.com.cn/blog/i207M/san-yuan-huan-ji-shuo-xue-xi-bi-ji