問題 atcoder.jp 解法 連結無向グラフから枝を取り除いていったときに非連結な頂点のペアの個数を答える問題.一般に，グラフから枝や頂点を取り除くという操作は難しいです. 逆に枝や頂点を追加するという操作は比較的かんたんです.今回の場合，枝を後ろから…

問題 D - 連結 / Connectivity 解法 鉄道が枝であるグラフと道路が枝であるグラフそれぞれでUnion-Findを行う。 頂点が鉄道と道路両方で連結であることは、がの同じ連結成分に含まれているかつの同じ連結成分に含まれている、ということと同値である。同じ連…

問題 D - Equals 解法 頂点集合が、枝集合がである無向グラフを考える。このときGの2つの頂点が同じ連結成分に含まれるならはスワップを何回か繰り返すことで値を入れ替える事ができる事がわかる(解説pdf)。よって頂点とが同じ連結成分に含まれているような…

問題 C - Bridge 解法 連結成分の数を数えればいいのでUnion-Findを使った。これでもACできるが、単に連結かどうか調べるだけなのでDFSで十分だしDFSのほうがやや計算量が小さい。 全ての枝に対して、元のグラフからその枝を取り除いたグラフが連結であるか…