מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם Union-Find/תרגילים/הוכחת נכונות Connected-Components/שאלה

נזכר בגרסה הראשונה שראינו של אלגוריתם Union-Find. משתמשים בה כך.

1	Sets = Connected-Components(G)

	# Prints True.
1	Print( Find-Set(Sets[1]) == Find-Set([3]) )

	# Prints False.
2	Print( Find-Set(Sets[2]) == Find-Set([3]) )

אנא הוכח את נכונות האלגוריתם, כלומר הראה שאכן

Find-Set(u) == Find-Set(v)

אמ"ם $\displaystyle u$ ו$\displaystyle v$ באותו רכיב קשירות.