求图上最小环
先介绍求类似与基环树上的环,每个点只有一条出边的环,:
这里以这道题P2661 [NOIP2015 提高组] 信息传递为例子
1dfs/bfs O(n)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int now,ans;
int a[N],b[N],f[N];
void dfs(int x,int d)
{
if(x==now)
{
ans=min(d,ans);
return ;
}
if(a[x]||b[x]) return ;
a[x]=1;
dfs(f[x],d+1);
a[x]=0;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&f[i]);
ans=0x3f3f3f3f;now=0;
for(now=1;now<=n;now++)
{
dfs(f[now],1);
b[now]=1;
}
printf("%d\n",ans);
}
2.tarjan O(n)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5+7, M = 4e5+7;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void tarjan(int u)
{
// printf("%d\n",u);
dfn[u] = low[u] = ++ timestamp;
stk[ ++ top] = u, in_stk[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!dfn[j])
{
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u])
{
++ scc_cnt;
int y;
do {
y = stk[top -- ];
in_stk[y] = false;
id[y] = scc_cnt;
Size[scc_cnt] ++ ;
} while (y != u);
}
}
int main()
{
memset(h, -1, sizeof h);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;scanf("%d",&x);
add(i,x);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
// printf("%d\n",scc_cnt);
// for(int i=1;i<=n;i++) printf("i:%d %d\n",i,low[i]);
int ans=0x3f3f3f3f;
for(int i=1;i<=scc_cnt;i++) if(Size[i]>1) ans=min(ans,Size[i]);
printf("%d\n",ans);
}
3.带权并查集 O(n)
就是维护并查集中点到根的距离,然后如果发现连个点在同一集合中,环的大小就是abs(d[i]-d[j])+1
并查集不好记录你求出来的环上的点有哪些
4.拓扑排序 O(n)可以解决无向图上的简单环的问题
对无向图进行拓扑排序,剩下的点就是一个强连通分量
有可能出现一个点在多个环上的时候:
5.最短路相关
(1)FloydO(n^3)
对于无向图是min(d[i,j]+a[j,k]+a[k,i]),对于有向图则直接求自己到自己的最短距离
ACwing344. 观光之旅
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=307;
int a[N][N],d[N][N],pos[N][N];
int ans;
vector<int> pa;
void getpa(int i,int j)
{
if(pos[i][j]==0) return;
getpa(i,pos[i][j]);
pa.pb(pos[i][j]);
getpa(pos[i][j],j);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
memset(a,0x3f,sizeof(a));
for(int i=1;i<=n;i++) a[i][i]=0;
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
a[u][v]=a[v][u]=min(a[u][v],w);
}
memcpy(d,a,sizeof(a));
ans=0x3f3f3f3f;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if((ll)d[i][j]+a[j][k]+a[k][i]<ans)
{
ans=d[i][j]+a[j][k]+a[k][i];
// printf("i:%d j:%d k:%d ans:%lld\n",i,j,k,ans);
pa.clear();
pa.pb(i);
getpa(i,j);
pa.pb(j);
pa.pb(k);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(d[i][j]>d[i][k]+d[k][j])
{
d[i][j]=d[i][k]+d[k][j];
pos[i][j]=k;
}
}
}
}
if(ans==0x3f3f3f3f) printf("No solution.\n");
else
{
for(int i=0;i<pa.size();i++) printf("%lld ",pa[i]);
printf("\n");
}
}
(2)dij
O(n^2logn) 的思路
1-n对所有点跑dij,每次跑完一个点,将他的dis置为无穷,再次跑到它时就得到经过它的最小环 这个不好跑无向图
O(n^2logn)的思路
每次断掉一个点的所有入边,对于剩下的图跑dij,此时得到的最小环就是(u,v)+dis
版权声明:本文为liangsheng_meng原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。