题意概述
给定一张 \(n\) 个顶点 \(m\) 条边的无向图，顶点的编号在 \(1 \sim n\) 内，第 \(i\) 条无向边连接着顶点 \(x_i\) 与 \(y_i\)。
我们称顶点 \(v_0,v_2,\cdots, v_{k-1}\) 构成了一个大小为 \(k\) 的环，当且仅当 \(k \ge 3\)，且对任意 \(0 \le i < k\)，图中都存在一条连接顶点 \(v_i\) 与 \(v_{(i+1) \operatorname{mod} k}\) 的无向边。我们称一个环 \(C\) 为最小环，当且仅当图中不存在一个大小严格小于 \(C\) 的环。
现在，你想要求出，图中有多少本质不同的最小环。
我们称两个环 \(C_1(u_0,u_1,\cdots, u_{k-1})\) 与 \(C_2(v_0,v_1,\cdots, v_{k-1})\) 不同，当且仅当组成这两个环的边不同。
输入格式
输入的第一行包含两个整数 \(n\) 和 \(m\) 。
接下来 \(m\) 行，每行两个整数 \(x, y\)，描述一条边。图中不包含重边与自环。
输出格式
输出一行一个整数，表示最小环的个数，不存在则输出 \(0\)。
样例一
输入
4 5
1 2
1 3
1 4
2 4
3 4
输出
2
样例二
输入
1000 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
输出
20
思路概述
考场的时候就想到了找包含每个点的环，但是当时为了保证一定经过这个点，还用了lca，甚至每次重新建树，复杂度是nm^2logm，只拿了35分，甚至还没单考虑三个点的环打暴力分数高。
正解
同样是找一定经过每个点的环，每次从当前点bfs，同时记录到该点的距离，如果往后bfs到了已经扫过的点，直接可以直接找到当前环的长度，如果比全局最小值小，就计数归零，否则计数累加即可
code
#include<bits/stdc++.h>
using namespace std;
const int N=3010,M=6010;
int n,m;
int minn=1e9,cnt;
int to[M<<1],nxt[M<<1],h[N],tot;
int dis[N],v[N],pre[N];
map<int,int> pot;
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}
void BFS(int X)
{
queue<int> q;
memset(v,0,sizeof v);
memset(dis,0x3f,sizeof dis);
memset(pre,0,sizeof pre);
q.push(X);
v[X]=1;
dis[X]=0;
while(q.size())
{
int x=q.front();
q.pop();
for(int i=h[x];i;i=nxt[i])
{
int y=to[i];
if(y==pre[x])continue;
if(!v[y])
{
v[y]=1;
dis[y]=dis[x]+1;
pre[y]=x;
q.push(y);
}else
{
if(dis[y]+dis[x]+1==minn)
{
cnt++;
}else if(dis[y]+dis[x]+1<minn)
{
minn=dis[y]+dis[x]+1;
cnt=1;
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
n=0;
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(!pot[x])pot[x]=++n;
if(!pot[y])pot[y]=++n;
x=pot[x],y=pot[y];
add(x,y);
add(y,x);
}
for(int i=1;i<=n;i++)BFS(i);
cout<<cnt/minn/2;
return 0;
}