D. Cow and Snacks

1700
  • Quiz
  • AC
  • 解説
    • 連結成分ごとに見たとき、「連結成分内のノード数-1」が幸せになる客の数、逆に言えばそれ以外の客は sad になる
  • その他
    • 「入次数が1のところから始めると良さそうだな？🤔」「dfsで探索して深さを出して🤔」とか考えたりもしましたが、dfsでカウントしようかと考えるときは、連結成分の数を見るだけで十分ってことは多い気がする
int main(){
    // input
    ll N,M;
    cin>>N>>M;

    UnionFind uf(N);

    rep(i,M){
      ll a,b;cin>>a>>b;
      a--;b--;
      uf.unite(a,b);
    }

    ll ans = M;
    auto mp = uf.getGroups();
    for(auto pa : mp){
      ans -= pa.second.size()-1;
    }
    p(ans);

    return 0;
}