发现环(lanqiao.cn)记录交接处,取出不属于环+邻接表不走回头路+set的遍历+进入该点再改其值。
作者:
dpking
,
2025-03-09 13:37:53
· 重庆
,
所有人可见
,
阅读 2
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
const int N=1e5+10;
vector<int> path[N]; //地图
int n;
int flag=false;
vector<int> temp; //局部路径随时变化
vector<int> res; //答案路径,局部路径符合就拿过来
int st[N]; //
int head; //最终搜到碰头的点即是中电,也是起点.就像6,前面有废物点。
void dfs(int u,int befor)
{
if(st[u]) //
{
flag=true;
res=temp;
head=u;
return;
}
st[u]=true; //到当前点了才改变,没走进去不改变。
temp.push_back(u);
for(int i=0;i<(int)path[u].size();i++)
{
if(befor==path[u][i]) continue; //不能走回头路
dfs(path[u][i],u);
if(flag) return;
}
st[u]=false;
temp.pop_back();
return;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a>>b;
path[a].push_back(b);
path[b].push_back(a);
}
for(int i=1;i<=n;i++)
{
if(flag) break;
memset(st,false,sizeof st);
dfs(i,-1);
}
bool can_out=false;
set<int> px;
for(int i=0;i<(int)res.size();i++) //筛出正确路径
{
if(head==res[i])
can_out=true;
if(can_out)
px.insert(res[i]);
}
for(set<int>::iterator it=px.begin();it!=px.end();it++)
{
cout<<*it<<" ";
}
return 0;
}