E 简单路径计数 - 第七届校赛正式赛 —— 补题
题目大意：
给一个简单无向图，图中有 N N N 个顶点，编号为 1 − N 1-N 1−N ，有 M M M 条边，编号为 1 − M 1-M 1−M 。边 i i i 连接顶点 u i u_i ui 和 v i v_i vi 。每个顶点的度数最多为 10 10 10 。
设 K K K 为从顶点 1 1 1 出发的简单路径（无重复顶点的路径）的数目，打印 m i n ( K , 1 0 6 ) min(K,10^6) min(K,106)。
1 < = K < = 1 0 6 1<=K<=10^6 1<=K<=106
1 < = K < = m i n ( 1 0 3 , N ∗ ( N − 1 ) / 2 ) 1<=K<=min(10^3,N*(N-1)/2) 1<=K<=min(103,N∗(N−1)/2)
1 < = u i , v i < = N 1<=u_i,v_i<=N 1<=ui,vi<=N
思路：
路径数最多 1 0 6 10^6 106 ，可以考虑搜索所有可行路径并进行剪枝
int ans=0,vis[N];
void dfs(int u){if(ans==1e6) return ;ans++;for(auto x:g[u]){if(vis[x]==0){vis[x]=1;dfs(x);vis[x]=0;//回溯路径if(ans==1e6) return ;}}
}
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define PII pair<int,int>
#define lowbit(x) x&-x
#define ALL(x) x.begin(),x.end()const int mod = 1e9 + 7;
const int N = 2e5 + 10;vector<int> g[N],vis(N);
int n,m,ans;void dfs(int u) {if(ans==1e6) return ;ans++; for(auto x:g[u]){if(vis[x]==0){vis[x]=1;dfs(x);vis[x]=0;}if(ans==1e6) return ;}
}void solve() {cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}vis[1]=1;dfs(1);cout<<ans<<'\n';
}signed main() {std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int T = 1;
// cin >> T;while (T--) {solve();}return 0;
}
