Subway

dfs找环的那个代码写的很烂= - =思路挺简单的,你找到环然后bfs一下就完事了

#include <bits/stdc++.h>
using namespace std;
const int N=3e3+5;
vector<int>v[N];
vector<int>cle;//存环上的点.
int dis[N];
int vis[N];
int flag=0,f=1;
void dfs(int u,int fa)
{
    if(flag) return;
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(x==fa) continue;
        if(vis[x]&&!flag) { flag=x;cle.push_back(u); return;}
        vis[x]=1;
        dfs(x,u);
    }
    if(u!=flag&&flag&&f) {cle.push_back(u);}
    if(u==flag) { cle.push_back(u);f=0; }
}
queue<int>q;
void bfs()
{
    while(q.size())
    {
        int temp=q.front();
        q.pop();
        for(int i=0;i<v[temp].size();i++)
        {
            int x=v[temp][i];
            if(dis[x]!=-1) continue;
            dis[x]=dis[temp]+1;
            q.push(x);
        }
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    vis[1]=1;
    dfs(1,0);//cout<<flag<<endl;
    memset(dis,-1,sizeof dis);
    //for(int i=0;i<cle.size();i++) cout<<cle[i]<<endl;
    for(int i=0;i<cle.size();i++)
    {
        q.push(cle[i]);
        dis[cle[i]]=0;
    }
    bfs();
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    puts("");
    return 0;
}