Number of Provinces

Q: ما هو التعقيد الزمني لمسألة عدد المقاطعات؟

‏O(n²) باستخدام البحث في الرسم البياني أو بنية الاتحاد-إيجاد، لأن كليهما يقرأ كل إدخال في المصفوفة n × n مرة واحدة. تضيف بنية الاتحاد-إيجاد العامل α(n)، وهو دالة أكرمان العكسية، والذي لا يتجاوز 4 عمليًا. المساحة الإضافية هي O(n).

Q: هل تستخدم DFS أم BFS أم union-find لإيجاد عدد المقاطعات؟

تعيد الطرق الثلاث العدد نفسه في زمن O(n²). كتابة DFS أو BFS هي الأقصر. وتكون بنية الاتحاد-إيجاد الخيار الأفضل عندما تحتاج أيضًا إلى الإجابة عن أسئلة كثيرة من نوع «هل تشترك هاتان المدينتان في مقاطعة؟»، لأن كل إجابة تستغرق زمنًا شبه ثابت.

Q: كيف يختلف عدد المقاطعات عن عدد الجزر؟

كلاهما يحسب المكونات المتصلة. في مسألة 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. لا يوجد طريق يصل بين الزوجين، لذا توجد مقاطعتان.

سؤال إضافي

يُفتح كل طريق الآن في يوم محدد. هل يمكنك إيجاد أول يوم تنتمي فيه جميع المدن إلى مقاطعة واحدة؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 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

بنية الاتحاد والعثور مع ضغط المسار والاتحاد حسب الرتبة

الفكرة

ابدأ بـ n مقاطعات، واحدة لكل مدينة. كل قيمة 1 فوق القطر تعني أن مدينتين تنتميان معًا إلى المجموعة نفسها: إذا اختلفت مجموعتاهما، فادمجهما وأنقص العدد بمقدار واحد. في المثال الثاني، يبدأ العدد عند 5، وتدمج (0, 1) المدينتين 0 و1، ثم تضم (1, 2) المدينة 2 إلى مجموعتهما، ويتبقى 3 مقاطعات.

تخزّن بنية الاتحاد-إيجاد كل مجموعة على هيئة شجرة: يشير parent[c] إلى العقدة الأعلى منه بخطوة واحدة، وتنتمي مدينتان إلى المجموعة نفسها عندما يصل بهما find إلى الجذر نفسه. إذا تُركت عمليات الدمج دون تحسين، فقد تكوّن مسارًا طويلًا واحدًا تسلكه كل عملية find في O(n) خطوة. يضع الاتحاد حسب الرتبة الشجرة الأقصر تحت الأطول، بحيث لا يتجاوز طول أي مسار log n. ويجعل ضغط المسار كل مدينة مرّت بها find تشير مباشرةً إلى الجذر. معًا، يجعلان كلفة كل find amortized 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

ما هو التعقيد الزمني لمسألة عدد المقاطعات؟

‏O(n²) باستخدام البحث في الرسم البياني أو بنية الاتحاد-إيجاد، لأن كليهما يقرأ كل إدخال في المصفوفة n × n مرة واحدة. تضيف بنية الاتحاد-إيجاد العامل α(n)، وهو دالة أكرمان العكسية، والذي لا يتجاوز 4 عمليًا. المساحة الإضافية هي O(n).

هل تستخدم DFS أم BFS أم union-find لإيجاد عدد المقاطعات؟

تعيد الطرق الثلاث العدد نفسه في زمن O(n²). كتابة DFS أو BFS هي الأقصر. وتكون بنية الاتحاد-إيجاد الخيار الأفضل عندما تحتاج أيضًا إلى الإجابة عن أسئلة كثيرة من نوع «هل تشترك هاتان المدينتان في مقاطعة؟»، لأن كل إجابة تستغرق زمنًا شبه ثابت.

كيف يختلف عدد المقاطعات عن عدد الجزر؟

كلاهما يحسب المكونات المتصلة. في مسألة 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]]

الإخراج المتوقع