Graph Valid Tree

Q: מהי סיבוכיות הזמן של Graph Valid Tree?

O(n + m) עם חיפוש לעומק, כאשר m הוא מספר הקשתות, ו־O(n + m α(n)) עם מבנה איחוד-חיפוש. בשתי הגישות בודקים תחילה את מספר הקשתות, ולכן גרף עם מספר שגוי נדחה לפני כל חיפוש.

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

+10

נתונים לך n צמתים, שממוספרים מ־0 עד n-1, ורשימה edges של קשתות לא מכוונות. כל זוג [a, b] מחבר בין הצומת a לצומת b.

החזר true אם הקשתות יוצרות עץ אחד מכל n הצמתים: אפשר להגיע מכל צומת לכל צומת אחר, ואין מעגל. אחרת, החזר false.

פונקציה

validTree(n: integer, edges: integer-2d-array) → boolean

ninteger: מספר הצמתים, הממוספרים מ־0 עד n-1
edgesinteger-2d-array: הקשתות הלא מכוונות, כל אחת זוג [a, b]
מחזירהboolean: true אם הקשתות מחברות את כל n הצמתים לעץ אחד, false אחרת

אילוצים

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [a, b] כאשר 0 ≤ a, b ≤ n-1 וגם a ≠ b
אף קשת אינה מופיעה פעמיים, בשום כיוון.

דוגמאות

קלט: n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
פלט: true
הסבר: צומת 0 מקושר לצמתים 1, 2 ו-3, וצומת 4 מחובר לצומת 1. ארבע קשתות מחברות את כל חמשת הצמתים ללא לולאה, ולכן זהו עץ.

קלט: n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
פלט: false
הסבר: הקשתות [1, 2], [2, 3] ו־[1, 3] יוצרות את הלולאה 1, 2, 3, 1. חמש קשתות בחמישה צמתים הן אחת יותר ממה שיכול להיות בעץ.

קלט: n = 4edges = [[0, 1], [1, 2], [2, 0]]
פלט: false
הסבר: יש 3 קשתות, כלומר n-1, אבל הן יוצרות את הלולאה 0, 1, 2, 0, ולצומת 3 אין שום קשת.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

עץ הוא קשיר ואין בו מעגל. כאשר יש בדיוק n-1 קשתות, אלה שני תנאים שקולים: גרף כזה קשיר אם ורק אם אין בו מעגל. לכן בדקו תחילה את מספר הקשתות, ואז חפשו פעם אחת אחר קשירות, או תנו ל-union-find לזהות קשת שמחברת שני צמתים שכבר מחוברים.

חפשו מסלול לפני כל צלע

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

הוסף את הקשתות אחת בכל פעם. לפני הוספת [u, v], חפש מ־u לאורך הקשתות שנוספו עד כה. אם ניתן להגיע אל v, הקשת החדשה יוצרת מסלול שני ביניהם וסוגרת מעגל, כפי שעושה [1, 3] בדוגמה השנייה. אם אף קשת אינה סוגרת מעגל, הגרף הוא יער, וחיפוש אחרון מהצומת 0 יגלה אם הוא עץ אחד.

כל בדיקה מחפשת בכל הגרף שנוצר עד כה. במסלול של 5001 צמתים שהקשתות שלו מגיעות לפי הסדר, החיפושים מבקרים ב־1 + 2 + ... + 5000 צמתים, כלומר כ־12.5 מיליון.

אלגוריתם

התחל עם רשימת שכנויות ריקה לכל צומת.
עבור כל קשת [u, v], חפש מ־u לאורך הקשתות שנוספו עד כה. אם מגיעים ל־v, החזר false.
אחרת, הוסף את הקשת לרשימות של שני הקצוות.
בסוף, החזר האם חיפוש מהצומת 0 מגיע לכל n הצמתים.

def reachable(graph, start):
    # Every node a search from start can reach, using the edges added so far.
    seen = [False] * len(graph)
    seen[start] = True
    stack = [start]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                stack.append(nxt)
    return seen


def validTree(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        # A path from u to v already exists, so this edge closes a cycle.
        if reachable(graph, u)[v]:
            return False
        graph[u].append(v)
        graph[v].append(u)
    # No cycle anywhere. A tree also needs every node reachable from node 0.
    return all(reachable(graph, 0))

ספרו את הצלעות, ואז חפשו פעם אחת

האינטואיציה

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

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

אלגוריתם

אם edges.length אינו n-1, החזר false.
בנה רשימת שכנויות, ושמור כל קשת תחת שני הקצוות שלה.
דחוף את הצומת 0 למחסנית וסמן אותו כמי שבוקר.
שלוף צמתים ודחוף כל שכן שטרם בוקר, תוך סימונו וספירתו בזמן הדחיפה.
החזר האם הספירה שווה ל־n.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    # With n-1 edges, the graph is a tree exactly when it is connected.
    seen = [False] * n
    seen[0] = True
    stack = [0]
    reached = 1
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if not seen[nxt]:
                seen[nxt] = True
                reached += 1
                stack.append(nxt)
    return reached == n

ספירת הצלעות ואיחוד־חיפוש

האינטואיציה

מבנה איחוד-חיפוש עונה על שאלת המחזור עבור כל קשת בלי לבצע חיפוש. כל צומת מתחיל כקבוצה בפני עצמה. עבור קשת [u, v], מוצאים את השורש של כל אחד משני הקצוות. שורשים שונים: הקשת מחברת שני חלקים, ולכן מאחדים אותם. אותו שורש: u ו-v כבר מחוברים, והקשת סוגרת מחזור. עם n-1 קשתות שכולן מאחדות קבוצות, n הקבוצות מסתיימות כקבוצה אחת: עץ.

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

אלגוריתם

אם edges.length אינו n-1, יש להחזיר false.
יש להגדיר parent[x] = x וגודל קבוצה של 1 עבור כל צומת.
עבור כל קשת [u, v], יש לעקוב אחר ההורים מ־u ומ־v עד לשורשים שלהם, ולהפנות כל צומת שעוברים דרכו אל הסבא שלו.
אם השורשים שווים: יש להחזיר false.
אם השורשים שונים: יש לחבר את שורש הקבוצה הקטנה יותר לשורש של הקבוצה האחרת ולהוסיף את הגודל שלה.
אם כל קשת איחדה שתי קבוצות, יש להחזיר true.

def validTree(n, edges):
    # A tree on n nodes has exactly n-1 edges.
    if len(edges) != n - 1:
        return False
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        # The two ends are already joined: this edge closes a cycle.
        if a == b:
            return False
        # Hang the smaller group under the larger one.
        if size[a] < size[b]:
            a, b = b, a
        parent[b] = a
        size[a] += size[b]
    # n-1 merges with no cycle turn the n groups into one.
    return True

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

בדיקה של מעגל בלבד. שלוש קשתות נפרדות בשישה צמתים אינן יוצרות מעגל, אך הן יוצרות שלושה רכיבים.
בדיקה של מספר הקשתות בלבד. בדוגמה השלישית יש n-1 קשתות, אבל הלולאה 0, 1, 2 משתמשת בקשת שנחוצה לצומת 3.
שמירת כל קשת תחת אחד הקצוות בלבד. גם [1, 0] מחברת בין הצמתים 0 ו-1, והחיפוש מהצומת 0 מחמיץ את הצומת 1.
בדיקת מעגל בעזרת חיפוש לעומק שאינה מדלגת על ההורה. כל קשת מובילה היישר בחזרה לצומת שממנו הגעת, ולכן התנאי "פגש שכן שכבר בוקר" מתקיים בכל עץ.
רקורסיה על מסלול ארוך. מסלול של 5001 צמתים מגיע לעומק של 5000 קריאות, מעבר למגבלת ברירת המחדל של 1000 ב-Python; השתמשו במחסנית מפורשת.

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

מהי סיבוכיות הזמן של Graph Valid Tree?

O(n + m) עם חיפוש לעומק, כאשר m הוא מספר הקשתות, ו־O(n + m α(n)) עם מבנה איחוד-חיפוש. בשתי הגישות בודקים תחילה את מספר הקשתות, ולכן גרף עם מספר שגוי נדחה לפני כל חיפוש.

למה לעץ עם n צמתים יש n-1 קשתות?

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

איך מזהים מעגל בגרף לא מכוון?

במבנה union-find, קשת ששני קצותיה כבר חולקים שורש סוגרת מעגל. בחיפוש לעומק, מעגל הוא שכן שביקרת בו ושאינו הצומת שממנו הגעת, ולכן עוקבים אחר ההורה של כל צומת. מבנה union-find אינו זקוק להורה או לרשימת שכנויות.

def validTree(n, edges):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

n = 5
edges = [[0, 1], [0, 2], [0, 3], [1, 4]]

הפלט הצפוי

true

Graph Valid Tree

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

חפשו מסלול לפני כל צלע

ספרו את הצלעות, ואז חפשו פעם אחת

ספירת הצלעות ואיחוד־חיפוש

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

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

בעיות דומות