度小满笔试记录-无向图回溯

感谢肖大佬的指导

题目大概就是：

有一个无向图，从节点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
*/