Number of Provinces

Q: מהי סיבוכיות הזמן של Number of Provinces?

‏O(n²) עם חיפוש בגרף או עם מבנה איחוד-חיפוש, כי שניהם קוראים כל ערך במטריצת n × n פעם אחת. מבנה איחוד-חיפוש מוסיף גורם α(n), פונקציית אקרמן ההפוכה, שהיא לכל היותר 4 בפועל. המקום הנוסף הוא O(n).

Q: האם כדאי להשתמש ב-DFS, ב-BFS או ב-union-find כדי לפתור את בעיית מספר המחוזות?

שלושתם מחזירים את אותה ספירה בזמן O(n²). הכי קצר לכתוב DFS או BFS. Union-find הוא הכלי המתאים יותר כשצריך גם לענות על שאלות רבות מהצורה "האם שתי הערים האלה שייכות לאותו מחוז", כי כל תשובה מתקבלת בזמן כמעט קבוע.

Q: במה שונה Number of Provinces מ-Number of Islands?

שתיהן סופרות רכיבים קשירים. בבעיה Number of Islands הגרף הוא רשת, לכל ריבוע יש לכל היותר ארבעה שכנים, וזמן העבודה הוא O(rows × cols). כאן הגרף הוא מטריצת שכנויות: כל עיר יכולה להיות מחוברת לכל עיר אחרת, ורישום השכנים של עיר אחת מצריך קריאה של שורה שלמה בת n ערכים.

בינוניאיחוד קבוצות גרפים

+10

יש n ערים, שממוספרות מ־0 עד n-1. isConnected[i][j] הוא 1 כאשר כביש מחבר ישירות בין עיר i לעיר j, ו־0 אחרת. הכבישים דו־כיווניים, ולכן המטריצה סימטרית, וכל עיר מחוברת לעצמה.

מחוז הוא קבוצה של ערים שכולן יכולות להגיע זו לזו, ישירות או דרך ערים אחרות, ואין כביש שמוביל אל מחוץ לקבוצה. החזירו את מספר המחוזות.

פונקציה

findCircleNum(isConnected: integer-2d-array) → integer

isConnectedinteger-2d-array: מטריצת n × n, 1 כאשר דרך מחברת ישירות בין שתי ערים
מחזירהinteger: מספר המחוזות

אילוצים

1 ≤ n ≤ 150, כאשר n = isConnected.length
isConnected[i].length = n
isConnected[i][j] הוא 0 או 1
isConnected[i][i] = 1
isConnected[i][j] = isConnected[j][i]

דוגמאות

קלט: isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]
פלט: 2
הסבר: לעיר 0 יש דרך לעיר 3, ולעיר 1 יש דרך לעיר 2. אין דרך שמחברת בין שני הזוגות, ולכן יש 2 מחוזות.

שאלת המשך

כל דרך נפתחת כעת ביום נתון. האם תוכל למצוא את היום הראשון שבו כל הערים שייכות לאותו מחוז?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

המטריצה מתארת גרף לא מכוון: הערים הן צמתים וכל 1 הוא קשת. מחוז הוא רכיב קשירות, ו־0 בין שתי ערים אינו מפריד ביניהן כאשר עיר שלישית מחברת את שתיהן. חיפוש מכל עיר שטרם ביקרנו בה, או מבנה איחוד־חיפוש על כל הקשתות, סופרים את הרכיבים ב־O(n²).

חיפוש לעומק מכל עיר שטרם ביקרו בה

האינטואיציה

עיר שלא סומנה לא יכולה להשתייך למחוז שכבר ספרת, כי כל חיפוש מסמן את המחוז כולו. לכן היא מתחילה מחוז חדש. החיפוש עוקב אחר שורות המטריצה: בדוגמה השנייה, החיפוש מעיר 0 מגיע לעיר 1, והשורה של עיר 1 מגיעה לאחר מכן לעיר 2, אף שבשורה 0 מופיע 0 עבור עיר 2.

כל עיר נשלפת פעם אחת וקוראת את השורה שלה, הכוללת n ערכים, כך שקוראים את המטריצה פעם אחת: זמן O(n²). הסימונים והמחסנית מכילים לכל היותר n ערים, ולכן הזיכרון הנוסף הוא O(n).

אלגוריתם

צרו דגל ביקור עבור כל עיר וקבעו את הספירה ל־0.
עברו על הערים לפי הסדר ודלגו על כל עיר שכבר בוקר בה.
בעיר שטרם בוקר בה, הוסיפו 1 לספירה, סמנו אותה ודחפו אותה למחסנית.
כל עוד יש ערים במחסנית, שלפו אחת ודחפו אליה כל עיר בשורה שלה שערכה 1 ושטרם בוקר בה, תוך סימונה בזמן הדחיפה.
החזירו את הספירה.

def findCircleNum(isConnected):
    n = len(isConnected)
    seen = [False] * n
    provinces = 0
    for start in range(n):
        if seen[start]:
            continue
        # Nobody reached this city from an earlier province, so it starts a new one.
        provinces += 1
        seen[start] = True
        stack = [start]
        while stack:
            city = stack.pop()
            row = isConnected[city]
            for other in range(n):
                # Mark a city when you push it, so it is never pushed twice.
                if row[other] == 1 and not seen[other]:
                    seen[other] = True
                    stack.append(other)
    return provinces

מבנה Union-find עם דחיסת מסלולים ואיחוד לפי דרגה

האינטואיציה

מתחילים עם n מחוזות, אחד לכל עיר. כל 1 מעל האלכסון מציין ששתי ערים שייכות לאותה קבוצה: אם הן בקבוצות שונות, מאחדים אותן ומפחיתים את הספירה באחד. בדוגמה השנייה הספירה מתחילה ב־5, (0, 1) מאחד את הערים 0 ו־1, (1, 2) מצרף את עיר 2 לקבוצה שלהן, ונשארים 3 מחוזות.

מבנה Union-find שומר כל קבוצה כעץ: parent[c] מצביע צעד אחד למעלה, ושתי ערים שייכות לאותה קבוצה כאשר find עובר בשתיהן עד לאותו שורש. ללא טיפול, פעולות האיחוד עלולות ליצור מסלול ארוך אחד שכל קריאה ל־find עוברת בו בצעדים של O(n). איחוד לפי דרגה מצרף את העץ הנמוך מתחת לגבוה, כך שאף מסלול אינו ארוך מ־log n. דחיסת מסלולים גורמת לכך שכל עיר שבה find עבר תצביע ישירות לשורש. יחד, הן מביאות לכך שהעלות הממוצעת לכל קריאה ל־find היא O(α(n)), ובפועל α(n) לכל היותר 4.

אלגוריתם

אתחלו parent[c] = c ו-rank[c] = 0 עבור כל עיר, ואת המונה ל-n.
עבור כל זוג i < j שעבורו isConnected[i][j] = 1, מצאו את השורשים של i ושל j.
ב-find, עלו עד לשורש, ואז עברו שוב לאורך הנתיב והפנו כל עיר שעליו אל השורש.
אם השורשים שונים, חברו את השורש בעל הדירוג הנמוך יותר מתחת לשני, הוסיפו 1 לדירוג במקרה של שוויון, והחסירו 1 מהמונה.
החזירו את המונה.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    rank = [0] * n

    def find(city):
        root = city
        while parent[root] != root:
            root = parent[root]
        # Path compression: point every city on the way straight at the root.
        while parent[city] != root:
            up = parent[city]
            parent[city] = root
            city = up
        return root

    provinces = n
    for i in range(n):
        for j in range(i + 1, n):  # the matrix is symmetric, so the upper half is enough
            if isConnected[i][j] == 1:
                a, b = find(i), find(j)
                if a == b:
                    continue
                # Union by rank: hang the shorter tree under the taller one.
                if rank[a] < rank[b]:
                    a, b = b, a
                parent[b] = a
                if rank[a] == rank[b]:
                    rank[a] += 1
                # Two provinces just became one.
                provinces -= 1
    return provinces

מלכודות ומקרי קצה

הסתמכות על כבישים ישירים בלבד. בין הערים 0 ו-2 בדוגמה השנייה מופיע 0, ובכל זאת הן שייכות לאותה פרובינציה.
ספירת ה-1-ים וחלוקה בשתיים. שלוש ערים שכולן מחוברות זו לזו יוצרות שלושה כבישים ופרובינציה אחת.
ב-union-find, הפחתת המונה בכל פעם שמופיע 1, במקום רק כשהשורשים של שתי הערים שונים.
השוואת parent[i] ל-parent[j]. לשתי ערים באותה קבוצה יכולים להיות הורים שונים אם אחת מהן נמצאת בעומק רב יותר; השוו בין find(i) ל-find(j).
חיבור העיר j עצמה, כמו ב-parent[j] = find(i). אם j כבר הייתה בקבוצה, שאר הקבוצה נשארת מחוץ לאיחוד.

שאלות נפוצות3

מהי סיבוכיות הזמן של Number of Provinces?

‏O(n²) עם חיפוש בגרף או עם מבנה איחוד-חיפוש, כי שניהם קוראים כל ערך במטריצת n × n פעם אחת. מבנה איחוד-חיפוש מוסיף גורם α(n), פונקציית אקרמן ההפוכה, שהיא לכל היותר 4 בפועל. המקום הנוסף הוא O(n).

האם כדאי להשתמש ב-DFS, ב-BFS או ב-union-find כדי לפתור את בעיית מספר המחוזות?

שלושתם מחזירים את אותה ספירה בזמן O(n²). הכי קצר לכתוב DFS או BFS. Union-find הוא הכלי המתאים יותר כשצריך גם לענות על שאלות רבות מהצורה "האם שתי הערים האלה שייכות לאותו מחוז", כי כל תשובה מתקבלת בזמן כמעט קבוע.

במה שונה Number of Provinces מ-Number of Islands?

שתיהן סופרות רכיבים קשירים. בבעיה Number of Islands הגרף הוא רשת, לכל ריבוע יש לכל היותר ארבעה שכנים, וזמן העבודה הוא O(rows × cols). כאן הגרף הוא מטריצת שכנויות: כל עיר יכולה להיות מחוברת לכל עיר אחרת, ורישום השכנים של עיר אחת מצריך קריאה של שורה שלמה בת n ערכים.

def findCircleNum(isConnected):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנט

isConnected = [[1, 0, 0, 1], [0, 1, 1, 0], [0, 1, 1, 0], [1, 0, 0, 1]]

הפלט הצפוי