2019-03-02から1日間の記事一覧
概要 N頂点M辺の無向グラフの連結成分のうち、閉路を持たないものの個数をもとめよ。 制約 1 ≦ N ≦ 100 1 ≦ M ≦ N(N-1)/2 方針 各頂点でDFSを行い、DFS内で1度通った頂点にまた通ることがあれば閉路を持つと判定する。 感想 昔解いたやつですが、備忘のため…
概要 N頂点M辺の無向グラフの連結成分のうち、閉路を持たないものの個数をもとめよ。 制約 1 ≦ N ≦ 100 1 ≦ M ≦ N(N-1)/2 方針 各頂点でDFSを行い、DFS内で1度通った頂点にまた通ることがあれば閉路を持つと判定する。 感想 昔解いたやつですが、備忘のため…