题目传送门
Problem - 131D - Codeforceshttps://codeforces.com/problemset/problem/131/D
https://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。
示例
| Inputcopy | Outputcopy |
|---|---|
4 1 3 4 3 4 2 1 2 | 0 0 0 0 |
| Inputcopy | Outputcopy |
|---|---|
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;
}
