AtCoder Beginner Contest 288C

ABC288C

DFSをして，すでに到達している頂点に到達したら， その辺はサイクルを作っているので除く辺となる． 同じ辺につき2回カウントするので2で割る．
この様な辺は，(向きも考慮するとき)後退辺と呼ぶらしい？

DFSにおける頂点，辺

dfs(cu, pa){

  // >>>

  // *** [頂点]に関する処理 (入ってきたとき)

  // <<<

 

  for(ne : to[cu]) if(ne != pa){ // 必要ならifをつける

    // >>>

    // *** [辺]に関する処理 (出るとき)

    // <<<

     

    dfs(ne, cu);

    // >>>

    // *** [辺]に関する処理 (出るとき)

    // <<<

     

  }

  // >>>

  // *** [頂点]に関する処理 (出るとき)

  // <<<

 

}

使っている記号，マクロ等 "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);

  }

 

  vll vis(n);

  ll cnt = 0;

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

    vis[cu] = true;

    for(auto ne: to[cu]) if(ne != pa){

      if(!vis[ne]){

        f(f,ne,cu);

      }else{

        cnt++;

      }

    }

  };

 

  rep(i,n) if(!vis[i]){

    dfs(dfs,i);

  }

  assert(cnt %2 == 0);

  cout << cnt/2 << endl;

  return 0;

}