洛谷P5022 旅行（基环树+断环法）

洛谷P5022 旅行（基环树+断环法）

​​原题链接​​题意： 一棵树，从1出发，每到达一个新的点就记录下编号。求一种走法使得记录下来的编号字典序最小。思路： 题意里说m<=n，就说明这棵树可能是基环树。 如果这棵树是普通的树的话，直接排序后dfs一下，每次都走字典序最小的点。如果这棵树是基环树的话，首先要明确一个性质，环上肯定有一条边是不经过的，可以手动模拟一下过程。所以我们就可以每次枚举这条不经过的边，求答案后取字典序最小。这条边不经过的话，对答案是无影响的，可以确保正确性。 复杂度大概n*n，吸吸氧气就能过。代码：

const int maxn=2e5+100;int h[maxn],idx;struct node{ int u,v,ne;}edge[maxn*2];int n,m;vectorg[maxn];void add(int u,int v){ edge[idx]={u,v,h[u]};h[u]=idx++;}int timetmp=0;int res[maxn],tmp[maxn],vis[maxn];void dfs(int u,int fa,int delu,int delv,int tmp[]){ if(vis[u]) return ; vis[u]=1; tmp[++timetmp]=u; for(int i=0;itmp[i]) return 1;//需要更改}int main(){ memset(h,-1,sizeof h); n=read(),m=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(); add(u,v);add(v,u); g[u].push_back(v); g[v].push_back(u); } for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());///对每个点的出边进行排序 if(n==m){///基环树 for(int i=0;i

​​参考：​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。