حلولي في كودرهب

هل يمكننا الوصول؟

صعب20 نقطةرياضياتPython

الوصف

تخيل أنك في مدينة تتكون من عدة أحياء (نسميها "الرؤوس")، وكل حي متصل ببعض الأحياء المجاورة عن طريق طرق ثنائية الاتجاه (نسميها "الحواف").

هدفك هو معرفة: هل يمكنك القيادة من الحي الذي تبدأ منه (المصدر) والوصول إلى حي معين آخر (الوجهة) باستخدام الطرق المتاحة؟

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

مثال توضيحي:

المدينة:

  • عدد الأحياء (الرؤوس): 5

  • الطرق (الحواف): [(0, 1), (1, 2), (2, 3), (3, 4)]

  • المصدر: 0

  • الوجهة: 4

الحل:

  • تبدأ من الحي 0.

  • تسير على الطريق إلى الحي 1.

  • من الحي 1، تسير إلى الحي 2.

  • من الحي 2، تسير إلى الحي 3.

  • وأخيرًا، تصل إلى الحي 4.

الإجابة: نعم، يمكنك الوصول إلى الحي 4!

ملاحظات:

  • كل طريق يمكن السير فيه في كلا الاتجاهين.

  • ليس كل الأحياء متصلة ببعضها.

  • الحل يعتمد على البحث الذكي (DFS أو BFS) لمعرفة إذا كان هناك مسار.

بالتوفيق في إيجاد الطريق!

أمثلة

المدخلاتالمخرجات المتوقعة
n = 3، edges = [0,1,1,2,2,0]، source = 0، destination = 2true
n = 6، edges = [0,1,0,2,3,5,5,4,4,3]، source = 0، destination = 5false
n = 1، edges = []، source = 0، destination = 0true
n = 2، edges = [0,1]، source = 0، destination = 1true

جرّب تحله في كودرهب

الحل

from typing import List
def validPath(n: int, edges: List[int], source: int, destination: int) -> bool:
    if source == destination:
        return True
    adj = [[] for _ in range(n)]
    for i in range(0, len(edges), 2):
        u, v = edges[i], edges[i+1]
        adj[u].append(v)
        adj[v].append(u)
    visited = set()
    stack = [source]
    while stack:
        node = stack.pop()
        if node == destination:
            return True
        if node in visited:
            continue
        visited.add(node)
        for neighbor in adj[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    return False

في هذه الصفحة