题目链接：
洛谷
Codeforces
Solution
Tarjan 板题。
很明显可以用 Tarjan 找到这一个环，由于这是一个无向图，所以需要多记录一个当前节点的父亲，防止其反复横跳。然后缩完点以后，找到一个强连通分量的大小大于 \(1\)，也就是那一个环，以它为源点，跑 dijkstra，与此同时把那个环里的点打上标记。最后输出时如果有标记，就输出 \(0\)，否则输出其最短路径。
Code
#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
char ch=getchar();
int r=0,w=1;
while(!isdigit(ch))w=ch=='-'?-1:1,ch=getchar();
while(isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
x=r*w;
}
const int N=1e5+7;
int low[N],dfn[N],stk[N],sz[N],scc[N];
int pre[N],now[N],son[N],dis[N],d[N];
int n,top,tot,sc,dfn_cnt;
bool in_stk[N],bb[N],cc[N];
vector<int>edge[N];
vector<int>in_h[N];
priority_queue<pair<int,int> >q;
void add(int x,int y,int z)
{
pre[++tot]=now[x];
son[tot]=y;
dis[tot]=z;
now[x]=tot;
}
void tarjan(int u,int fa)
{
low[u]=dfn[u]=++dfn_cnt;stk[++top]=u;in_stk[u]=1;
for(int v:edge[u])
{
if(v==fa)continue;
if(!dfn[v])
{
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
else if(in_stk[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u])
{
sc++;
do
{
scc[stk[top]]=sc;
in_h[sc].push_back(stk[top]);
sz[sc]++;
in_stk[stk[top]]=0;
top--;
}while(stk[top+1]!=u);
}
}
void dij(int s)
{
memset(d,63,sizeof d);
d[s]=0;q.push(make_pair(0,s));
while(!q.empty())
{
int u=q.top().second;q.pop();
if(bb[u])continue;
bb[u]=1;
for(int i=now[u];i;i=pre[i])
{
int v=son[i],w=dis[i];
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
q.push(make_pair(-d[v],v));
}
}
}
}
void work()
{
for(int u=1;u<=n;u++)
for(int v:edge[u])
if(scc[u]!=scc[v])add(scc[u],scc[v],1),add(scc[v],scc[u],1);
}
int main()
{
read(n);
for(int i=1,x,y;i<=n;i++)
{
read(x);read(y);
edge[x].push_back(y);edge[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
work();
for(int i=1;i<=sc;i++)
{
if(sz[i]>1)
{
for(int j:in_h[i])cc[j]=1;
dij(i);
break;
}
}
for(int i=1;i<=n;i++)
printf("%d ",cc[i]==1?0:d[scc[i]]);
return 0;
}