正题

题目链接:https://www.luogu.com.cn/problem/AT2368

---

题目大意

给出 $n$ 个点 $m$ 条边的一张无向图，然后求一条路径满足

• 路径长度不小于二。
• 路径无交。
• 对于所有的 $x$ 与路径的端点相连，那么 $x$ 在路径上。

$1\le n,m\le 10^5$

---

解题思路

还是利用到那个经典的性质，就是$dfs$树上所有非树边都是返祖边。

首先如果$dfs$树的根只有一条出边那么以这个点为起点到达任意一个叶子都是合法的。

但是如果有两个或者以上的出边，我们可以连接两个叶子就好了。

时间复杂度：$O(n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e5+10; struct node{int to,next; }a[N<<1]; int n,m,tot,lf,ls[N],v[N],fa[N]; queue<int> q; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } int dfs(int x){int z=0;v[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y])continue;fa[y]=x;dfs(y);z++;}if(!z)lf=x;return z; } void path(int x,bool flag){v[x]=1;q.push(x);if(fa[x]&&flag){path(fa[x],1);return;}for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(v[y])continue;path(y,0);break;}return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addl(x,y);addl(y,x);}dfs(1);memset(v,0,sizeof(v));path(lf,1);printf("%d\n",q.size());while(!q.empty())printf("%d ",q.front()),q.pop();return 0; }

总结

以上是生活随笔为你收集整理的AT2368-[AGC013B]Hamiltonish Path【构造】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。