🔲

ABC284-C: Count Connected Components 解説

2023/01/08に公開

問題

N頂点M辺の単純無向グラフが与えられます.
連結成分の個数を求めてください.
https://atcoder.jp/contests/abc284/tasks/abc284_c

解説

  • UnionFindを使った典型的な問題です
    • DFSやBFSを使って連結している頂点を見つける方法でもできます
  • UnionFind(Disjoint Set Union, dsu)は次の操作を高速に行うことができるデータ構造(?)です
    1. (Union) ある2つの要素を同じグループにする
    2. (Find) ある2つの要素が同じグループに存在するか判定する
    • 詳しくはググるとたくさんの先人の知恵があります.
  • 今回の問題では,ある辺で繋がれた2つの頂点を同じグループにして,最終的にグループが何個あるか判定すれば良いです.
  • AtCoderにはAtCoder Libraryというものが存在し,そのなかのdsuを用いると便利です.
    • groupsという関数が用意されていて,そのサイズを出力するだけになります

コード

https://atcoder.jp/contests/abc284/submissions/37863681

GitHubで編集を提案

Discussion

ログインするとコメントできます