度小满笔试记录-无向图回溯
2023-02-18 16:41:46 时间
感谢肖大佬的指导
题目大概就是:
有一个无向图,从节点1开始,遍历所有其他节点有几种方法
思路就是回溯,从1开始深度遍历,使用计数法统计所有节点
#include<bits/stdc++.h>
using namespace std;
const int maxn=55;
int b[maxn],n,m,ans=0;
vector<int>vv[maxn];
void dfs(int pos,int cnt){
if(cnt==n){
ans++;
return ;
}
for(int i=0;i<vv[pos].size();i++){
int tt=vv[pos][i];
if(b[tt]==0){
b[tt]=1;
dfs(tt,cnt+1);
b[tt]=0;
}
}
return ;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
vv[x].push_back(y);
vv[y].push_back(x);
}
memset(b,0,sizeof(b));
b[1]=1;
dfs(1,1);
// //若不从1开始则有如下 ,且最后ans/2(去重)
// for(int i=1;i<=n;i++){
// b[i]=1;
// memset(b,0,sizeof(b));
// dfs(i,0);
// }
cout<<ans<<endl;
}
/*
4 6
1 2
1 3
1 4
2 4
2 3
3 4
1 2 3 4
1 2 4 3
1 3 4 2
1 4 3 2
1 3 2 4
1 4 2 3
*/
相关文章
- 论文速递2022.8.17!
- Disco Diffusion VS Stable Diffusion效果对比! 论文速递2022.8.18!
- 论文速递2022.8.19!
- 论文速递2022.8.22!
- 论文速递2022.8.23!
- DataGrip激活码,DataGrip2022最新_DataGrip使用说明
- 帅爆! 赛博朋克特效实现
- 论文速递2022.8.24!
- STABLE Diffusion 权重公布! 注册可下载使用论文速递2022.8.25!
- 论文速递2022.8.26!
- CVPR2022 | 视频摩尔纹去除 ! 论文速递2022.8.29!
- [javaEE] EL表达式调用java方法
- 赛博朋克特效实现 ! 附源码
- [javaEE] EL表达式获取数据
- 输入位置,控制 StyleGAN 生成图像的布局! 论文速递2022.8.31!
- 论文速递2022.9.1!
- 论文速递2022.9.2!
- X-NeRF!一种基于神经辐射场公式的学习交叉光谱场景表示的新方法! 论文速递2022.9.5!
- ECCV2022 | SimpleRecon 无需 3D 卷积的高质量三维重建方案! 论文速递2022.9.7!
- 交通灯数据集,涵盖城市和郊区! 论文速递2022.9.8!