# ABC049 D - 連結

# 概要

NN個の都市とKK本の道路とLL本の鉄道が伸びている.
ii本目の道路はpip_iqiq_i番目の都市を, jj本目の鉄道はrir_isis_i番目の鉄道を結んでいる.

全ての都市について, 道路と鉄道の両方で連結している都市の数を求めよ.

  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 1K,L1051 \leq K, L \leq 10^5

# 解法

  • 連結かつ制約からUnion-Findを使いそう
  • roadとtrainでUnion-Find木を作る
  • どうやって全ての都市について, 道路と鉄道の両方で連結しているかを確認するんだ?
  • ~20分経過~~~~~~
  • editorialを見る
  • 道路と鉄道のpairでカウントするらしい
  • なぜそうなった?
  • これでした
  • 言い換えると, 道路と鉄道で同じ根を持つ時に, 道路と鉄道の両方で連結していると言えるから

# 提出

ABC049-D

# ref.

Last Updated: 2019-3-14 02:04:59