前言
环是普通图区别于部分特殊图的原因，学会在图上高效且正确的找到或者判断各种环是有必要的。
本文介绍作者见过的那些有向图，无向图上各种找环判环问题和解决方案。
可通过点选右侧导航栏来翻看你想要的内容。
work in progress...
图上环的定义
如果你直接看一个图那么环的定义是显然的。
但是形式化定义还是要给一下的：
给定图 \(G = (V, E)\)，一个简单环是顶点序列 \(v_0, v_1, \ldots, v_k\) 满足：
\(v_0 = v_k\)（闭合），
对任意 \(0 \leq i < j \leq k\)，若 \(i \neq 0\) 或 \(j \neq k\)，则 \(v_i \neq v_j\)（顶点不重复），
边集 \(\{v_i v_{i+1} \mid 0 \leq i < k\}\) 无重复。
有向图中的环都是有方向的，你可以认为无向图中的环是没有方向的。
判断有向图中是否存在环
当然可以简单的用一遍 DFS 判断，但是递归常数大。
Show me the code
#include
using namespace std;
const int N=1e5+5;
vector
bool vis[N];
bool dfs(int u){
for(auto v:edge[u]){
if(vis[v])return 1;
vis[v]=1;
if(!vis[v]&&dfs(v))return 1;
}
return 0;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
edge[u].push_back(v);
}
for(int i=1;i<=n;i++){
if(!vis[i]&&dfs(i)){
cout<<"circuit";
return 0;
}
}
cout<<"no";
return 0;
}
还记得拓扑排序吗，如果拓扑排序可以遍历到所有的点，也可以证明原图没有环，反之也可以证明原图有环。
Show me the code
#include
using namespace std;
const int N=1e5+5;
vector
int inner[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
edge[u].push_back(v);
inner[v]++;
}
queue
for(int i=1;i<=n;i++){
if(inner[i]==0)q.push(i);
}
int cnt=0;
while(q.size()){
int u=q.front();q.pop();
cnt++;
for(auto v:edge[u]){
inner[v]--;
if(inner[v]==0)q.push(v);
}
}
if(cnt!=n)cout<<"circuit";
else cout<<"no";
return 0;
}
判断无向图中是否存在环
当然可以简单的用一遍 DFS 判断，但是递归常数大。
Show me the code
#include
using namespace std;
const int N=1e5+5;
vector
bool vis[N];
bool dfs(int u){
for(auto v:edge[u]){
if(vis[v])return 1;
vis[v]=1;
if(!vis[v]&&dfs(v))return 1;
}
return 0;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i=1;i<=n;i++){
if(!vis[i]&&dfs(i)){
cout<<"circuit";
return 0;
}
}
cout<<"no";
return 0;
}
考虑环上的每一个点在无向图上至少拥有两个度，因此类似拓扑排序，我们每次循环去掉度小于二的点，并对周围它的临界点的度数减。如果在这样的情况下能够遍历到所有点，就可以证明原图中没有环。
注意因为是无向图要另外开一个数组记录各点是否被删除，避免死掉。
Show me the code
#include
using namespace std;
const int N=1e5+5;
vector
int inner[N];bool del[N];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
inner[v]++;inner[u]++;
}
queue
for(int i=1;i<=n;i++){
if(inner[i]<=1){q.push(i);del[i]=1;}
}
int cnt=0;
while(q.size()){
int u=q.front();q.pop();
cnt++;
for(auto v:edge[u]){
if(del[v])continue;
inner[v]--;
if(inner[v]<=1){q.push(v);del[v]=1;}
}
}
if(cnt!=n)cout<<"circuit";
else cout<<"no";
return 0;
}
找图的最小环长
一个简单环的环长定义为这个环上的边的边权之和。
这个东西目前没什么高妙的做法，暴力的尝试断开每一条有向边 \((i,j)\)，计算在断开这个边后的图上 \(i\) 到 \(j\) 的最短路，那么加上这个边就是一个经过 \(i,j\) 的最小环了。
这样，图上每个边都断一遍，取最小即得图中最小环长。
如果图比较特殊，可以使用对应比较特殊的求解最短路的方法求解最短路。
若使用优先队列优化的 Dijkstra 算法，时间复杂度为 \(O(m^2 \log m)\)
如果是在无向图上，一次断掉两条边即可（尽管一次断掉一条边也是对的）。辛苦点用链式前向星存图就可以一次断掉两条边了。
当然，由于这个算法基于边，因此还是用对边管理比较准确的链式前向星存图比较好。
下面的代码例是在边权恒定为 \(1\) 的无向图上，用了一半（？）的链式前向星存图的找最小环算法。
Show me the code
#define rd read()
#include
using namespace std;
typedef long long ll;
int n,m;
const int N=7000;
struct e{
int u,v,eid;
}ei[N*2];
vector
ll sakanaction=0;
void bfs(int s,int ban,int t){
queue
memset(dii,0x3f,sizeof dii);
dii[s]=0;
while(q.size()){
int u=q.front();
if(u==t)break;
q.pop();
for(int i=0;i int v=edge[u][i].v; int eid=edge[u][i].eid; if (eid==ban) continue;// 不能通过被断掉的边 if(dii[v]>dii[u]+1){ dii[v]=dii[u]+1; q.push(v); } } } return ; } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; u=rd;v=rd; edge[u].push_back(e{u,v,i});edge[v].push_back({v,u,i*2}); ei[i].u=u;ei[i].v=v;ei[i].eid=i; ei[i+m].u=v;ei[i+m].v=u;ei[i+m].eid=i*2; } int k=0x3f3f3f3f; for(int i=1;i<=m*2;i++){ bfs(ei[i].u,ei[i].eid,ei[i].v); k=min(k,abs(dii[ei[i].u]-dii[ei[i].v])+1); } cout< return 0; } 图上最小环计数 NCPC 2022 E. Enigmatic Enumeration 首先先应用上面的找最小环长算法找到这个图的最小环长。 你会发现如果想要一次就不重不漏的找到所有环是很难做的，因此我们试试先不考虑重复，找到从每一点开始的最小环的数量。 因为最小环上有环长这么多个点，因此每个环一定会被多统计环长遍，把这样计算出的环数量除以环长就是答案。 现在考虑从一个点出发计算经过这个点的最小环数量，这好像依然非常难办。我们一般处理环问题都是断环成链的，因此这里我们把这个环分成二分之环长的两部分。这里涉及一个奇偶性讨论，为了方便我们先让环长 \(k\) 是个偶数，这样环就被我们分解为两条长度为 \(\frac{k}{2}\) 的简单路径。 你会发现这两条简单路径都是从指定的点出发的，并且会与另外一点。 这让我们想到，可以考虑计算从这一点出发，到每个点的长度为 \(\frac{k}{2}\) 的不同简单路径的条数，这样就可以应用乘法原理计算可能的环的数量了。 细节上说，我们从选定点的每一个出点开始寻找长度为 \(\frac{k}{2}\) 的路径，这一过程 DFS 是好做的。经过 \(\frac{k}{2}\) 找到一点时，这个点之前记录的路径数就都不是从这个出点出发的了，因此可以大胆认为组成了路径数量的环，然后累加但不并入之前记录的路径数。当前出点遍历完后，再并入之前记录的路径数。 现在你应该明白大致原理了。若环长为奇数，只需要统计 \(\frac{k}{2}\) 路径数，但再走到 \(\frac{k}{2}+1\) 长度的路径时再计算即可。 code Show me the code #define rd read() #include using namespace std; typedef long long ll; ll read(){ ll x=0,f=1; char c=getchar(); while(c>'9'||c<'0'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m; const int N=7000; struct e{ int u,v,eid; }ei[N*2]; int dii[N]; vector ll sakanaction=0; void bfs(int s,int ban,int t){ queue q.push(s); memset(dii,0x3f,sizeof dii); dii[s]=0; while(q.size()){ int u=q.front(); if(u==t)break; q.pop(); for(int i=0;i int v=edge[u][i].v; int eid=edge[u][i].eid; if (eid==ban) continue; if(dii[v]>dii[u]+1){ dii[v]=dii[u]+1; q.push(v); } } } return ; } int vis[N]; int toti[N],subr[N]; void dfs1(int u,int d,int md){ if(d==md){subr[u]++;return ;} for(int i=0;i int v=edge[u][i].v; if(vis[v])continue; vis[v]=1; dfs1(v,d+1,md); vis[v]=0; } } void dfs2(int u,int d,int md){ if(d==md){subr[u]++;return ;} else if(d==md-1){sakanaction+=toti[u];} for(int i=0;i int v=edge[u][i].v; if(vis[v])continue; vis[v]=1; dfs2(v,d+1,md); vis[v]=0; } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; u=rd;v=rd; edge[u].push_back(e{u,v,i});edge[v].push_back({v,u,i*2}); ei[i].u=u;ei[i].v=v;ei[i].eid=i; ei[i+m].u=v;ei[i+m].v=u;ei[i+m].eid=i*2; } int k=0x3f3f3f3f; for(int i=1;i<=m*2;i++){ bfs(ei[i].u,ei[i].eid,ei[i].v); k=min(k,abs(dii[ei[i].u]-dii[ei[i].v])+1); } if(k%2==0){ for(int i=1;i<=n;i++){ memset(toti,0,sizeof toti); vis[i]=1; for(int j=0;j int v=edge[i][j].v; memset(subr,0,sizeof subr); dfs1(v,1,k/2); for(int pp=1;pp<=n;pp++){ sakanaction+=toti[pp]*subr[pp]; toti[pp]+=subr[pp]; } } vis[i]=0; } } else{ for(int i=1;i<=n;i++){ memset(toti,0,sizeof toti); vis[i]=1; for(int j=0;j int v=edge[i][j].v; memset(subr,0,sizeof subr); dfs2(v,1,k/2+1); for(int pp=1;pp<=n;pp++){ toti[pp]+=subr[pp]; } } vis[i]=0; } } cout< return 0; } 图中判断是否存在奇环偶环 还记得二分图的一个性质吗： 理论判定：不存在奇数长度回路的图一定是二分图。特殊的：没有环的图也一定是二分图 于是判断二分图的过程就是判断奇环的过程。黑白染色法即可。 Show me the code #include using namespace std; const int N=1e5+5; vector int col[N]; bool dfs(int u,int c){ for(auto v:edge[u]){ if(!col[v]){ col[v]=3-c; if(dfs(v,3-c))return 1; } else if(col[v]!=3-c)return 1; } return 0; } int main(){ int n,m; for(int i=1;i<=m;i++){ int u,v;cin>>u>>v; edge[u].push_back(v); edge[v].push_back(u); } for(int i=1;i<=n;i++){ if(!col[i]&&dfs(i,1)){ cout<<"odd"; return 0; } } cout<<"even"<<' '; return 0; } 判偶环，那么如果图里没有奇环但是有环那么就是偶环了。 基环树上找环 无向图中的简单环计数 无向图中的三元环计数 无向图中的四元环计数