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

מהתבוננות בConnected-Components, ברור ש6 מתבצעת פעם אחת לכל קשת. מכאן נקבל שמספר הקריאות לFind-Set הוא $\displaystyle 2\cdot |E|$.

עפ"י נתוני השאלה, הגרף המתקבל מהאלגוריתם הוא יער של $\displaystyle k$ עצים. לפי המשפט שלמדנו לגבי הקשר בין מספר הקשתות לצמתים בעצים, סך מספר הקשתות בעצים הוא $\displaystyle |V|-k$, ולכן זהו מספר הפעמים שUnion ייקרא (כל פעולת Union, הרי, מייצרת קשת אחת).