[過去ﾛｸﾞ] スレ立てるまでもない質問はここで 158匹目 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

371(1): 2021/12/11(土)00:00 ID:L5jxStGt(1) AAS
ふとお題がどっちなのか気になった
x1 = X(1, 2)
x2 = X(2, 3)
もし有向で、a同士が一致しない、b同士も一致しないから同じグループにはしない、という要件の場合、Union-Findの応用で解けるんだろうか

---

372: 2021/12/11(土)12:36 ID:yVS9OnV5(1) AAS
>>371
disjoint setとは別にaとbの各値がどのグループに属するかを配列で管理すればいいと思う

0番目:(1, 2)
a[1] == -1 && b[2] == -1なので a[1] = 0, b[2] = 0

1番目:(2, 3)
a[2] == -1 && b[3] == -1なので a[2] = 1, b[3] = 1

2番目:(1, 6)
a[1] != -1 && b[6] == -1なので b[6] = a[1], union(a[1], 2)

3番目:(2, 6)
a[2] != -1 && b[6] != -1なので root = union(a[2], b[6]), a[2] = root, b[6] = root, union(root, 3)

2番目・3番目の最後のunionはroot設定専用の関数でも可

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 1.848s*