免费网站服务器软件下载大全,做网站店铺装修的软件,设计发布平台,公明网站建设公司正题
题目链接:https://www.luogu.com.cn/problem/AT2368 题目大意
给出 nnn 个点 mmm 条边的一张无向图#xff0c;然后求一条路径满足
路径长度不小于二。路径无交。对于所有的 xxx 与路径的端点相连#xff0c;那么 xxx 在路径上。 1≤n,m≤1051\leq n,m\leq 10^51≤n,…正题
题目链接:https://www.luogu.com.cn/problem/AT2368 题目大意
给出 nnn 个点 mmm 条边的一张无向图然后求一条路径满足
路径长度不小于二。路径无交。对于所有的 xxx 与路径的端点相连那么 xxx 在路径上。
1≤n,m≤1051\leq n,m\leq 10^51≤n,m≤105 解题思路
还是利用到那个经典的性质就是dfsdfsdfs树上所有非树边都是返祖边。
首先如果dfsdfsdfs树的根只有一条出边那么以这个点为起点到达任意一个叶子都是合法的。
但是如果有两个或者以上的出边我们可以连接两个叶子就好了。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1e510;
struct node{int to,next;
}a[N1];
int n,m,tot,lf,ls[N],v[N],fa[N];
queueint q;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
int dfs(int x){int z0;v[x]1;for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y])continue;fa[y]x;dfs(y);z;}if(!z)lfx;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 ils[x];i;ia[i].next){int ya[i].to;if(v[y])continue;path(y,0);break;}return;
}
int main()
{scanf(%d%d,n,m);for(int i1;im;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;
}
