AtCoder Beginner Contest 284E

ABC284E

Simple path の個数
DFS で求まる．今の頂点 \(cu\) からの遷移が終わった後に， \(vis[cu] = false\) に戻す． 別の path で同じ頂点 \(cu\) に来た場合，区別して数えるから．

実装
戻り値に答えを入れた． つまり，戻り値に対して \(chmin(cnt, 1e6)\) を入れる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n, m ;

  cin >> n >> m;

  vvll to(n);

  rep(i,m){

    ll a,b; cin >> a >> b;

    --a, --b;

    to[a].push_back(b);

    to[b].push_back(a);

  }

  vector<bool> vis(n);

  auto dfs = [&](auto dfs, ll cu, ll pa = -1, ll cnt = 0) -> ll {

    if(cnt >= 1e6) return cnt ;

    if(vis[cu]) return cnt;

    vis[cu] = true;

    for(auto ne: to[cu]) {

      cnt = dfs(dfs, ne, cu, cnt);

    }

    vis[cu] = false; // do not forget

    return min(cnt+1, ll(1e6)); // do not forget

  };

  ll cnt = dfs(dfs,0);

  // assert(cnt <= 1e6);

  cout << cnt << endl;  

 

  return 0;

}