Number of Provinces

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

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

Q: هل ينبغي استخدام DFS أم BFS أم union-find لحل مسألة Number of Provinces؟

تعيد الطرق الثلاث كلها العدد نفسه بزمن O(n²). وتكون كتابة DFS أو BFS أقصر عندما تُعطى المصفوفة كاملة دفعة واحدة. ويكون Union-find الأداة الأفضل عندما تصل الطرق واحدة تلو الأخرى، أو عندما تحتاج أيضًا إلى الإجابة عما إذا كانت مدينتان تنتميان إلى المقاطعة نفسها، لأنه يتعامل مع كل طريق وكل سؤال في زمن يقترب من الثابت دون إجراء بحث جديد.

Q: ما وظيفة ضغط المسار والاتحاد حسب الرتبة في بنية الاتحاد-البحث؟

يربط الاتحاد حسب الرتبة الشجرة الأقصر أسفل الشجرة الأطول عند دمج مجموعتين، مما يحافظ على ارتفاع كل شجرة بحيث لا يتجاوز log n. يجعل ضغط المسار كل عقدة يمر بها find تشير مباشرةً إلى الجذر، لذا تستغرق عمليات البحث اللاحقة من تلك العقد خطوة واحدة. باستخدام التقنيتين معًا، تبلغ كلفة أي سلسلة من m عمليات O(m α(n))، وهو ما يعادل تقريبًا زمنًا خطيًا.

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

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

+15 اختبارات مخفية عند الإرسال

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

المصفوفة هي مصفوفة المجاورة لرسم بياني غير موجّه: المدن هي العُقد، ويمثّل الرقم 1 في الصف i والعمود j ضلعًا. والمقاطعة مكوّن متصل، لذا فإن الإجابة هي عدد المكوّنات. تكمن الخدعة في إمكان الوصول عبر مدينة ثالثة: فوجود 0 بين مدينتين لا يعني أنهما تنتميان إلى مقاطعتين مختلفتين. إن إجراء بحث انطلاقًا من كل مدينة لم تتم زيارتها، أو استخدام بنية الدمج والبحث التي تدمج طرفَي كل ضلع، يحصي المكوّنات في O(n²)، وهو حجم المصفوفة نفسها.

البحث بالعمق من كل مدينة لم تُزَر

الفكرة

مرّ على المدن بالترتيب. عندما تصادف مدينة لم يسبق لأي بحث أن علّمها، فلا يمكن أن تكون جزءًا من مقاطعة سبق أن حسبتها، لأن كل بحث يعلّم جميع مدن مقاطعته. لذا أضف واحدًا إلى العدد، ثم علّم كل مدينة يمكن لهذه المدينة الوصول إليها.

للعثور عليها، استخدم مكدسًا. أخرج مدينة من المكدس، واقرأ صفّها في المصفوفة، وأضف إلى المكدس كل مدينة تحتوي خانتها في ذلك الصف على 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). لا توجد قيمة 1 فوق القطر للمدينتين 3 و4، لذا فالإجابة هي 3.

تخزّن بنية الاتحاد-البحث، التي تُسمّى أيضًا اتحاد المجموعات المنفصلة، كل مجموعة على شكل شجرة. يشير parent[c] خطوة واحدة إلى الأعلى، والمدينة الموجودة في القمة، والتي يكون أبُوها هي نفسها، هي جذر المجموعة. تكون مدينتان في المجموعة نفسها بالضبط عندما تصعد بهما find إلى الجذر نفسه. لدمج مجموعتين، اجعل أحد الجذرين يشير إلى الآخر.

تحافظ قاعدتان على تسطّح الأشجار. الاتحاد حسب الرتبة يعلّق الشجرة الأقصر أسفل الأطول، لذا تحتوي شجرة ارتفاعها h على الأقل على 2^h مدينة، ولا يزيد طول أي مسار عن log n. أما ضغط المسار فيذهب إلى أبعد من ذلك: فبعد أن تعثر find على الجذر، تجعل كل مدينة مرّت بها تشير مباشرةً إلى ذلك الجذر، وبذلك يستغرق البحث التالي من أيٍّ منها خطوة واحدة. من دون أي من القاعدتين، يؤدي دمج مدن سلسلة طويلة بترتيب غير موفق إلى إنشاء شجرة ليست سوى مسار واحد، ويستغرق كل find عدد O(n) من الخطوات.

مع تطبيق القاعدتين، تبلغ كلفة كل find، بمعدلها على المدى الطويل، O(α(n))، حيث α هي دالة أكرمان العكسية، وتظل قيمتها 4 أو أقل لأي n يستطيع الحاسوب تخزينه. تظل قراءة المصفوفة تتطلب O(n²)، لذا فهذه هي الكلفة الإجمالية، وتستهلك مصفوفتا parent وrank مساحة 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 لحل مسألة Number of Provinces؟

تعيد الطرق الثلاث كلها العدد نفسه بزمن O(n²). وتكون كتابة DFS أو BFS أقصر عندما تُعطى المصفوفة كاملة دفعة واحدة. ويكون Union-find الأداة الأفضل عندما تصل الطرق واحدة تلو الأخرى، أو عندما تحتاج أيضًا إلى الإجابة عما إذا كانت مدينتان تنتميان إلى المقاطعة نفسها، لأنه يتعامل مع كل طريق وكل سؤال في زمن يقترب من الثابت دون إجراء بحث جديد.

ما وظيفة ضغط المسار والاتحاد حسب الرتبة في بنية الاتحاد-البحث؟

يربط الاتحاد حسب الرتبة الشجرة الأقصر أسفل الشجرة الأطول عند دمج مجموعتين، مما يحافظ على ارتفاع كل شجرة بحيث لا يتجاوز log n. يجعل ضغط المسار كل عقدة يمر بها find تشير مباشرةً إلى الجذر، لذا تستغرق عمليات البحث اللاحقة من تلك العقد خطوة واحدة. باستخدام التقنيتين معًا، تبلغ كلفة أي سلسلة من m عمليات O(m α(n))، وهو ما يعادل تقريبًا زمنًا خطيًا.

ما الفرق بين عدد المقاطعات وعدد الجزر؟

كلاهما يحسب المكوّنات المتصلة. في مسألة عدد الجزر، يكون الرسم البياني شبكةً، ولكل مربع أربعة جيران على الأكثر، ويكون العمل 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]]

المتوقع