DFS wa 70求调 ! ! ! !
查看原帖
DFS wa 70求调 ! ! ! !
1382982
jikky楼主2024/11/19 16:58
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int tot=0,head[N];
int d[N],faa[N];
int cnt=0;
int ans[N];
struct E{
	int ne;
	int v;
}e[N<<2];
void add(int u,int v){
	e[++tot].ne=head[u];
	e[tot].v=v;
	head[u]=tot;
}
void push(int x,int y){//找到LCA并把路径上的点加入答案 
	if(d[x]>d[y]) swap(x,y);
	while(d[y]>d[x]){
		ans[++cnt]=y;
		y=faa[y];
	}
	while(y!=x){
		ans[++cnt]=y;
		ans[++cnt]=x;
		y=faa[y];
		x=faa[x];
	}
	ans[++cnt]=x;
	sort(ans+1,ans+cnt+1);//从小到大输出 
	for(int i=1;i<=cnt;i++){
		cout<<ans[i]<<" ";
	}
	return;
}
void dfs(int u,int fa){
	d[u]=d[fa]+1;//计算深度 
	faa[u]=fa;//记录父亲 
	for(int i=head[u];i;i=e[i].ne){
		if(e[i].v!=fa){
			if(d[e[i].v]!=0){
				push(e[i].v,u);
				exit(0);
			}
			dfs(e[i].v,u);
		}
	}
	
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	d[0]=-1;
	dfs(1,0);
	return 0;
}
2024/11/19 16:58
加载中...