求 hack
查看原帖
求 hack
602803
_qingshu_楼主2024/11/12 10:56
#include<bits/stdc++.h>
using namespace std;
mt19937 rd(time(0));
int n,Min[1200010];
vector<int>e[1200010]; 
inline void getMin(int id,int fa){
	if(e[id].size()<=2)Min[id]=id;
	else Min[id]=INT_MAX;
	for(auto v : e[id]){
		if(v==fa)continue;
		getMin(v,id);
		Min[id]=min(Min[id],Min[v]);
	}
}
inline void dfs(int id,int fa,int flag,int i=0,int j=0){
	if(e[id].size()==0){
		cout<<id<<" ";
	}
	else if(e[id].size()==1){
		cout<<id<<" ";
		if(!fa)dfs(e[id][0],id,1);
	}
	else if(e[id].size()==2){
		if(!fa){
			cout<<id<<" ";
			for(;i<e[id].size();i++)
				if(e[id][i]!=fa)
					break;
			for(;j<e[id].size();j++)
				if(e[id][j]!=fa&&j!=i)
					break;
			if(Min[e[id][i]]<Min[e[id][j]])
				dfs(e[id][i],id,0),
				dfs(e[id][j],id,1);
			else
				dfs(e[id][j],id,0),
				dfs(e[id][i],id,1);
		}
		else if(flag){
			cout<<id<<" ";
			for(;i<e[id].size();i++)
				if(e[id][i]!=fa)
					break;
			if(Min[e[id][i]]<e[id][i])
				dfs(e[id][i],id,0);
			else
				dfs(e[id][i],id,1);
		}
		else{
			for(;i<e[id].size();i++)
				if(e[id][i]!=fa)
					break;
			if(id<Min[e[id][i]])
				cout<<id<<" ",dfs(e[id][i],id,0);
			else
				dfs(e[id][i],id,0),cout<<id<<" ";
		}
	}
	else{
		if(flag)cout<<id<<" ";
		for(;i<e[id].size();i++)
			if(e[id][i]!=fa)
				break;
		for(;j<e[id].size();j++)
			if(e[id][j]!=fa&&j!=i)
				break;
		if(Min[e[id][i]]<Min[e[id][j]]){
			dfs(e[id][i],id,0);
			if(!flag)cout<<id<<" ";
			dfs(e[id][j],id,flag);
		}
		else{
			dfs(e[id][j],id,0);
			if(!flag)cout<<id<<" ";
			dfs(e[id][i],id,flag);
		}
	}
}
int main(){
//	freopen("c.in","r",stdin);
//	freopen("c.out","w",stdout);
	cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		for(int j=1,y;j<=x;j++)
			cin>>y,
			e[i].emplace_back(y);
	}int rt=1;
	for(rt=1;rt<=n;rt++)if(e[rt].size()!=3)break;
	getMin(rt,0);dfs(rt,0,1);
}
2024/11/12 10:56
加载中...