题目传送门

Problem - 131D - Codeforceshttps://codeforces.com/problemset/problem/131/Dhttps://codeforces.com/problemset/problem/131/D

翻译

地铁方案，对于Berland城市来说是一种经典的表示，由一组n站点和连接这些站点的n通道组成，每个通道连接两个站点，不经过其他任何站点。此外，在经典方案中，可以沿着通道从任意一个站点到达任何其他站点。通道可以双向移动。在每对站点之间最多只有一条通道。

Berland的数学家最近证明了一个定理，即任何经典方案都有一个环路。只能有一个环路。换句话说，在任何经典方案中，都可以找到仅由站点组成的方案（其中任意相邻的两个站点都由通道连接），并且此循环不包含任何站点超过一次。

这一发明对社会产生了巨大的影响，因为现在可以根据站点距离环路的远近进行比较。例如，一个市民可以说“我离环路有三个通道”，另一个人可以回答“你这个失败者，我离环路只有一个通道”。很快，互联网上充斥着承诺计算站点到环路距离的应用程序（向短号码发送短信...）。

Berland政府决定结束这些干扰，并开始控制局势。要求你编写一个程序，可以确定城市地铁方案中每个站点距离环路的远近。

输入

第一行包含一个整数n（3 ≤ n ≤ 3000），n是地铁方案中站点（同时也是列车）的数量。然后n行包含列车的描述，每行包含一对整数xi, yi（1 ≤ xi, yi ≤ n），表示从站点xi到站点yi有一条通道。站点按任意顺序编号为1到n。保证xi ≠ yi，并且没有一对站点包含多于一条通道。通道可以双向使用。保证给定的描述表示一个经典地铁方案。

输出

打印n个数字。用空格分隔这些数字，第i个数字应等于第i个站点距离环路的距离。对于环路上的站点，打印数字0。

示例

4
1 3
4 3
4 2
1 2

0 0 0 0 

6
1 2
3 4
6 4
2 3
1 3
3 5

思路

先找到图中的唯一环，然后从环出发进行 BFS，得到其他点到环的距离

共计两次 BFS，详情如下

怎么找环

不断从图中删掉出度为 1 的点，删到不能再删为止，剩下的一定都是环上的点

为什么这么做可以找到环？核心思路是删掉不在环上的点，保留在环上的点

画个符合题意的图分析一下，不难得出，环上的点出度不小于 2，出度为 1 的一定不是环上的点

直接删掉出度为 1 的点

随着出度为 1 的点被不断删除，原先出度不小于 2 的不在环上的点的出度也会减到 1，最终被删掉

环上的点不会在此过程中被删掉，最终留下的有且仅有环上的点

怎么实现上述找环过程

以下简称出度为 1 的点为 x，其通向的点为 y

怎么实现删掉 x

"删掉" 的目的是使原先出度不小于 2 的不在环上的点的出度减小，最终成为 x

因此，删掉 x，只需要删掉 y 通向 x 的边，y 的出度就减小了，就达到了 "删掉" 的目的

怎么删掉所有不在环上的点

一次 BFS 即可解决，BFS 前先入队当前所有的 x

对于队列中的每个 x，删掉 y 通向 x 的边，然后判断 y 的情况并做出相应反应，之后出队 x

如果 y 的出度减小到 1，说明 y 也不在环上，y 成为了 x，入队 y

如果 y 的出度大于 1，暂时不管它。如果 y 在环上，那么它的出度永远不会小于 2

否则 y 的出度有朝一日会减小到 1，到时候再收拾它

循环体中，执行出队操作时就标记出队的点不是环上的点

这样循环结束后根据标记就能区分某点在不在环上

找完环之后怎么办

找到环上的点后，以所有环上的点为起点，BFS 一次就得到答案了

第一次 BFS 删除点的操作，会影响第二次 BFS。因此要记录被删掉的边

第二次 BFS 前重新加上被删掉的边即可

代码

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 3005;
vector<int> g[N];
vector<PII> del;
int n, q[N], head, tail = -1, dist[N];
bool cycle[N], mk[N];
void BFS1()
{for (int i = 1; i <= n; i++) //入队所有出度为 1 的点if (g[i].size() == 1)q[++tail] = i;while (head <= tail) //BFS 标记并删掉所有不在环上的点{int x = q[head++], y = g[x][0]; //因为 x 出度只有 1，所以用不着循环cycle[x] = true; //cycle[i] == true 表示点 i 不在环上del.push_back({ y,x }); //记录删除操作g[y].erase(find(g[y].begin(), g[y].end(), x)); //删掉 y 通向 x 的边if (g[y].size() == 1) q[++tail] = y; //如果 y 的出度减小到 1，入队 y}
}
void BFS2()
{head = 0, tail = -1;for (int i = 1; i <= n; i++) //入队并标记所有环上的点，以它们为起点if (cycle[i] == false)q[++tail] = i, mk[i] = true;for (auto& z : del) g[z.first].push_back(z.second); //撤销删除操作while (head <= tail) //BFS 计算距离模板{int x = q[head++];mk[x] = true;for (auto y : g[x]){if (mk[y] == false){q[++tail] = y;mk[y] = true;dist[y] = dist[x] + 1;}}}
}
int main()
{scanf("%d", &n);for (int i = 0; i < n; i++){int x, y;scanf("%d%d", &x, &y);g[x].push_back(y);g[y].push_back(x);}BFS1();BFS2();for (int i = 1; i <= n; i++) printf("%d ", dist[i]);return 0;
}