Number of Provinces

Q: מהי סיבוכיות הזמן של מספר המחוזות?

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

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

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

Q: מה עושים דחיסת מסלולים ואיחוד לפי דרגה במבנה איחוד-חיפוש?

איחוד לפי דרגה מחבר את העץ הקצר יותר מתחת לעץ הגבוה יותר כששתי קבוצות מתאחדות, וכך הגובה של כל עץ נשאר לכל היותר log n. דחיסת נתיבים גורמת לכל צומת ש- find עובר דרכו להצביע ישירות על השורש, ולכן חיפושים מאוחרים יותר מאותם צמתים דורשים צעד אחד. בשילוב של שתי השיטות, כל רצף של m פעולות עולה O(m α(n)), התנהגות שדומה לזמן ליניארי.

Q: במה שונה מספר המחוזות ממספר האיים?

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

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

+10

יש n ערים, שממוספרות מ־0 עד n-1. נתונה לך מטריצה בגודל n × n בשם isConnected כרשימה של שורות: 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 מחוזות.

+15 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

האינטואיציה

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

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

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

חיפוש רקורסיבי קריא יותר, אבל במחוז שצורתו קו ארוך, הקריאות נערמות פעם אחת לכל עיר. כאשר n = 150, זה בטוח; אותו קוד בגרף עם 10^5 צמתים יגרום לגלישת מחסנית הקריאות, ולכן כדאי להקפיד להשתמש במחסנית מפורשת.

אלגוריתם

צרו דגל ביקור עבור כל עיר ואתחלו את הספירה ל־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

איחוד-חיפוש עם דחיסת מסלולים ואיחוד לפי דרגה

האינטואיציה

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

מבנה איחוד־חיפוש, שנקרא גם איחוד קבוצות זרות, שומר כל קבוצה כעץ. parent[c] מצביע צעד אחד כלפי מעלה, והעיר שבראש העץ, שההורה שלה הוא היא עצמה, היא השורש של הקבוצה. שתי ערים נמצאות באותה קבוצה בדיוק כאשר find מעלה את שתיהן לאותו שורש. כדי לאחד שתי קבוצות, מצביעים מאחד השורשים אל האחר.

שני כללים שומרים על העצים שטוחים. איחוד לפי דרגה מצרף את העץ הנמוך יותר מתחת לגבוה יותר, כך שעץ בגובה h מכיל לפחות 2^h ערים, ואף מסלול אינו ארוך מ־log n. דחיסת מסלולים מרחיקה לכת עוד יותר: לאחר ש־find מצא את השורש, הוא מצביע מכל עיר שבה עבר ישירות אל השורש, כך שהחיפוש הבא מכל אחת מהן דורש צעד אחד. ללא אף אחד מהכללים האלה, מיזוג הערים בשרשרת ארוכה בסדר לא מוצלח בונה עץ שהוא מסלול יחיד, וכל find עובר O(n) צעדים.

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

אלגוריתם

הגדר 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 כהוכחה ששתי ערים מופרדות, או סופרות משהו אחר במקום רכיבי קשירות.

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

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

מהי סיבוכיות הזמן של מספר המחוזות?

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

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

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

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

איחוד לפי דרגה מחבר את העץ הקצר יותר מתחת לעץ הגבוה יותר כששתי קבוצות מתאחדות, וכך הגובה של כל עץ נשאר לכל היותר log n. דחיסת נתיבים גורמת לכל צומת ש-find עובר דרכו להצביע ישירות על השורש, ולכן חיפושים מאוחרים יותר מאותם צמתים דורשים צעד אחד. בשילוב של שתי השיטות, כל רצף של m פעולות עולה O(m α(n)), התנהגות שדומה לזמן ליניארי.

במה שונה מספר המחוזות ממספר האיים?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

קלט

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

צפוי