解题思路:使用一个bool已经dfs来判断环上点的位置,详细的看代码上的注释
注意事项:
参考代码:
#include<bits/stdc++.h>
#define DZT ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int N =1e5+5;
bool ed[N],flag;//ed数组用记录该店是否来过 flag用来判断是否发现了环
int fa[N];
vector<int> m[N];
vector<int> ans;
int n,k;//k表示找到了环的一个节点
void dfs(int now,int f){
fa[now]=f;//利用fa数组来记录路径
if(ed[now]){flag=true;k=now; return;}
ed[now]=true;
for(int i:m[now]){
if(flag){return;}//已经发现了环上的点了就没有必要继续后面的搜索了
if(i==f) continue;
dfs(i,now);
}
}
signed main()
{
DZT//别在意这个
cin>>n;
for(int i=1;i<=n;i++){
int x,y; cin>>x>>y;
m[x].push_back(y);
m[y].push_back(x);
}
dfs(1,0);
int t=k;
while(fa[t]!=k){//将路径上的点保存到ans中
ans.push_back(t);
t=fa[t];
}
ans.push_back(t);//记住别漏了一个
sort(ans.begin(),ans.end(),less<int>());//排序一下
for(int i:ans){
cout<<i<<" ";
}
return 0;
}
0.0分
0 人评分
C二级辅导-分段函数 (C语言代码)浏览:868 |
破解简单密码 (C语言代码)浏览:1772 |
c primer plus 第十二章 12.1小节浏览:377 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:549 |
2004年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:1341 |
字符串比较 (C语言代码)浏览:693 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:471 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:566 |
简单的a+b (C语言代码)浏览:466 |
剔除相关数 (C语言代码)浏览:1095 |