【题目来源】https://www.luogu.com.cn/problem/P8655【题目描述】小明的实验室有 N 台电脑编号 1∼N。原本这 N 台电脑之间有 N−1 条数据链接相连恰好构成一个树形网络。在树形网络上任意两台电脑之间有唯一的路径相连。不过在最近一次维护网络时管理员误操作使得某两台电脑之间增加了一条数据链接于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径使得这些电脑上的数据传输出现了 BUG。为了恢复正常传输。小明需要找到所有在环路上的电脑你能帮助他吗【输入格式】第一行包含一个整数 N。以下 N 行每行两个整数 a 和 b表示 a 和 b 之间有一条数据链接相连。输入保证合法。【输出格式】按从小到大的顺序输出在环路上的电脑的编号中间由一个空格分隔。【输入样例】51 23 12 42 55 3【输出样例】1 2 3 5【说明/提示】对于 30% 的数据1≤N≤1000。对于 100% 的数据1≤N≤10^51≤a,b≤N。时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛。【算法分析】● 基环树https://blog.csdn.net/hnjzsyjyj/article/details/167919947● DFS栈记录法步骤1维护 DFS 递归栈 path保存当前的搜索路径使用数组 inStack[] 标记顶点是否位于递归栈内。2访问邻接点 v若 v 尚未被访问则递归遍历若 v 已访问且在栈内说明找到一条回边栈中从 v 到栈顶的片段即为环。3截取该栈片段提取得到环上顶点的有序序列 ring[]。【算法代码一DFS栈记录法】#include bits/stdc.h using namespace std; const int N1e55; vectorint g[N],path; bool vis[N],inStk[N],onRing[N]; vectorint ring; bool dfs(int u,int fa) { vis[u]inStk[u]true; path.push_back(u); for(int v:g[u]) { if(vfa) continue; if(!vis[v]) { if(dfs(v,u)) return true; } else if(inStk[v]) { int pos0; while(path[pos]!v) pos; for(int ipos; ipath.size(); i) { ring.push_back(path[i]); onRing[path[i]]true; } return true; } } path.pop_back(); inStk[u]false; return false; } int main() { int n,x,y; cinn; for(int i1; in; i) { cinxy; g[x].push_back(y); g[y].push_back(x); } dfs(1,-1); for(int i1; in; i) { if(onRing[i]) couti ; } return 0; } /* in: 5 1 2 3 1 2 4 2 5 5 3 out: 1 2 3 5 */【算法代码拓扑剥叶法】→https://blog.csdn.net/hnjzsyjyj/article/details/167918148#include bits/stdc.h using namespace std; const int N1e55; vectorint g[N]; int deg[N]; bool onRing[N]; void findRing(int n) { queueint q; for(int i1; in; i) { onRing[i]true; if(deg[i]1) { onRing[i]false; q.push(i); } } while(!q.empty()) { int uq.front(); q.pop(); for(int v:g[u]) { if(!onRing[v]) continue; if(--deg[v]1) { onRing[v]false; q.push(v); } } } } int main() { int n,x,y; cinn; for(int i1; in; i) { cinxy; g[x].push_back(y); g[y].push_back(x); deg[x], deg[y]; } findRing(n); for(int i1; in; i) { if(onRing[i]) couti ; } return 0; } /* in: 5 1 2 3 1 2 4 2 5 5 3 out: 1 2 3 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/167919947https://blog.csdn.net/hnjzsyjyj/article/details/140716866https://www.cnblogs.com/pure4knowledge/p/18211724https://www.cnblogs.com/yifan0305/p/17506679.htmlhttps://blog.csdn.net/ZhuRanCheng/article/details/131736222