蓝桥杯 17.发现环

发现环

原题目链接

题目描述

小明的实验室有 N 台电脑，编号 1 ⋯ N。

原本这 N 台电脑之间有 N−1 条数据链接相连，恰好构成一个树形网络。
在树形网络上，任意两台电脑之间有唯一的路径相连。

不过在最近一次维护网络时，管理员误操作，使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。

环路上的电脑由于两两之间不再只有一条路径，使得这些电脑上的数据传输出现了 BUG。

为了恢复正常传输，小明需要找到所有在环路上的电脑。你能帮助他吗？

---

输入描述

• 第一行包含一个整数 N，表示电脑数量。
• 接下来的 N 行，每行包含两个整数 a, b，表示 a 和 b 之间有一条数据链接相连。

数据范围：

• 1 ≤ N ≤ 10⁵
• 1 ≤ a, b ≤ N

输入保证数据合法，即原本是一棵树，恰好多出一条边形成一个环。

---

输出描述

按从小到大的顺序输出所有在环路上的电脑的编号，用空格分隔。

---

输入样例

5
1 2
3 1
2 4
2 5
5 3

---

输出样例

1 2 3 5

---

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int a, b, x;int main() {int N;scanf("%d", &N);vector<vector<int>> arr(N + 1);vector<int> d(N + 1, 0), ans;for (int i = 0; i < N; i++) {scanf("%d %d", &a, &b);arr[a].push_back(b), arr[b].push_back(a), d[a]++, d[b]++;}queue<int> qu;for (int i = 1; i <= N; i++) {if (d[i] == 1) qu.push(i);}while(!qu.empty()) {x = qu.front(), qu.pop(), d[x]--;for (int y : arr[x]) {d[y]--;if (d[y] == 1) qu.push(y);}}for (int i = 1; i <= N; i++) {if (d[i] > 1) ans.push_back(i);}sort(ans.begin(), ans.end());for (int i = 0; i < ans.size(); i++) {printf("%d", ans[i]);if (i != ans.size() - 1) printf(" ");}return 0;
}//by wqs

题目解析

判断一个图是否有环，依次删除度为 1 的点以及与其相连的边，这样可以把所有不成环的链上点依次删除，最后也无法被删除的点集就是题目要求的答案，按照编号从小到大输出即可。

具体步骤

1、统计所有点的入度；
2、创建一个队列维护所有入度为 1 的点，将所有度等于 1 的节点加入队列。（本题中没有独立的节点，所以不用考虑度为 0 的情况）；
3、当队列不为空时，弹出队首元素，把与队首元素相邻的节点入度减 1，如果相邻节点度数变为 1，则将相邻节点加入队列；
4、循环结束后，从小到大判断每个结点的入度，若入度大于 1，则说明该节点在环内，输出该节点。