图论 - 最短路 - dfs - 基环树 - bfs
做法应该很明显了,把环找出来求最短路就可以了,重点是怎么找环
这里讲的是一个
O
(
n
2
)
O(n^2)
O(n2) 的神奇 dfs,非常容易写
思路与 dfs/spfa 找环很相似,只不过不需要判断最短路
void dfs(int x,int fa,int top) // fa,top 分别为上一个访问的节点和该次dfs的第一个节点
{
flag[x]=1; // 打上标记
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
if(y==fa)continue;
if(flag[y]) //如果已经访问过了
{
if(y==top)opt2=1; // 这个判断的意义,是为了保证已经打上标记的所有点都在环上
opt1=1; // 打上退出递归的标记
return;
}
dfs(y,x,top);
if(opt1)return;
}
flag[x]=0;
}
跑完 dfs 后,所有环上的点都被标记了,然后将它们塞进队列跑 dijkstra 就可以了
其实 bfs 也行,因为是无权图
#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int Maxn=3020,inf=0x3f3f3f3f;
struct node{
int pos,dis;
node(int x,int y)
{
pos=x,dis=y;
}
bool operator <(const node &x)const
{
return x.dis<dis;
}
};
int dis[Maxn];
bool vis[Maxn],flag[Maxn],opt1,opt2;
int n;
vector <int> e[Maxn];
inline int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
void dfs(int x,int fa,int top)
{
flag[x]=1;
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
if(y==fa)continue;
if(flag[y])
{
if(y==top)opt2=1;
opt1=1;
return;
}
dfs(y,x,top);
if(opt1)return;
}
flag[x]=0;
}
void dij()
{
priority_queue <node> q;
fill(dis+1,dis+1+n,inf);
for(int i=1;i<=n;++i)
{
if(!flag[i])continue;
dis[i]=0,vis[i]=1;
q.push(node(i,0));
}
while(q.size())
{
int x=q.top().pos;
q.pop();
for(int i=0;i<e[x].size();++i)
{
int y=e[x][i];
if(dis[y]>dis[x]+1)
{
dis[y]=dis[x]+1;
if(!vis[y])vis[y]=1,q.push(node(y,dis[y]));
}
}
}
}
int main()
{
// freopen("in.txt","r",stdin);
n=read();
for(int i=1;i<=n;++i)
{
int x=read(),y=read();
e[x].push_back(y);
e[y].push_back(x);
}
for(int i=1;i<=n;++i)
{
opt1=0;
dfs(i,0,i);
if(opt2)break; // opt2=1 说明已经找到了环,并且保证标记无误
fill(flag+1,flag+1+n,0); // 记得将标记清零
}
dij();
for(int i=1;i<=n;++i)
printf("%d ",dis[i]);
putchar('\n');
return 0;
}