[ABC284E] Count Simple Paths 题解

FFTotoro · 2023-01-14 18:00:15 · 题解

本题可以使用深度优先搜索解决。

每遍历到一个点，计数器自增 1，然后就去找没有走过且相邻的点。

因为本题的特殊约束“每个顶点度 \le 10”，所以可以放心地直接搜索。

如果搜的点数量大于 10^6，那就直接输出 10^6 并用 exit(0) 强制结束程序即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
vector<int> g[200001];
bool b[200001];
int c=0;
void dfs(int u){
  if(++c>=1e6)cout<<(int)1e6<<endl,exit(0);
  for(int i:g[u])
    if(!b[i])b[i]=true,dfs(i),b[i]=false;
  return;
}
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m; cin>>n>>m;
  for(int i=1;i<=m;i++){
    int u,v; cin>>u>>v;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  b[1]=true; dfs(1);
  cout<<c<<endl;
  return 0;
}