关于 dfs
  • 板块学术版
  • 楼主wo_hen_la
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/8/25 21:43
  • 上次更新2024/8/26 09:03:39
查看原帖
关于 dfs
794701
wo_hen_la楼主2024/8/25 21:43

为什么这个死循环了,

#include <bits/stdc++.h>
using namespace std;

#define sp putchar(' ')
#define en putchar('\n')
#define pb push_back
#define int long long
#define P 998244353
#define HP 1000000000000002097
#define N (int)(2e5+5)

int read(){ char ch=getchar();int x=0,f=1;while(ch>'9' || ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f; }
void print(int x){ if(x<0) putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0'); }

int n;
vector<int> e[N];
struct node
{
	int vv,siz;
}a[N]; 
bool cmp(node x,node y)
{
	return x.siz>y.siz;
}
int mx=0;
void dfs(int u,int fa,int ti)
{
	//cout<<u<<"\n";
	mx=max(mx,ti);
	int cnt=0;
	for(auto v:e[u]){
		if(v==fa) continue;
		//dfs(v,u,ti);
		a[++cnt].vv=v;
		a[cnt].siz=e[v].size()-1;
	}
	if(cnt==0) return;
	sort(a+1,a+1+cnt,cmp);
	for(int i=1;i<=cnt;i++) cout<<a[i].vv<<" "<<a[i].siz<<"\n";
	for(int i=1;i<=cnt;i++){
		dfs(a[i].vv,u,++ti);
		//cout<<a[i].siz<<" ";
	}
}
signed main()
{
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2,u;i<=n;i++){
		cin>>u;
		e[u].pb(i);e[i].pb(u);
	}
	/*for(int i=1;i<=n;i++){
		for(auto v:e[i]) cout<<v<<" ";
		cout<<"\n";
	}*/
	dfs(1,0,1);
	/*int ans=1e9;
	for(int i=1;i<=n;i++){
		mx=0;
		dfs(i,0,1);
		ans=min(ans,mx);
		cout<<mx<<" ";
	}
	cout<<ans<<"\n";*/
	return 0;
}
2024/8/25 21:43
加载中...