หลักสูตรคู่ขนานในภาษา Python

สมมติว่ามีหลักสูตร N และสิ่งเหล่านี้มีป้ายกำกับตั้งแต่ 1 ถึง N นอกจากนี้เรายังให้อาร์เรย์ความสัมพันธ์โดยที่ความสัมพันธ์[i] =[X, Y] แสดงถึงความสัมพันธ์ข้อกำหนดเบื้องต้นระหว่างหลักสูตร X และหลักสูตร Y ดังนั้นนี่หมายความว่า ต้องเรียนหลักสูตร X ก่อนหลักสูตร Y

ในภาคการศึกษาหนึ่ง เราสามารถเรียนหลักสูตรจำนวนเท่าใดก็ได้ ตราบใดที่เราได้ศึกษาข้อกำหนดเบื้องต้นทั้งหมดสำหรับหลักสูตรที่เรากำลังศึกษาอยู่ เราต้องหาจำนวนภาคการศึกษาขั้นต่ำที่จำเป็นในการเรียนทุกหลักสูตร และถ้าไม่มีทางเรียนครบทุกรายวิชาก็คืนค่า -1

ดังนั้นหากอินพุตเป็น N =3 ความสัมพันธ์ =[[1,3],[2,3]] ผลลัพธ์จะเป็น 2 เช่น ในภาคการศึกษาแรกจะมีการศึกษาหลักสูตรที่ 1 และ 2 ในภาคเรียนที่ 2 จะเรียนหลักสูตรที่ 3

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• รายวิชา :=n

• เยี่ยมชม :=อาร์เรย์ขนาด n+1 และเติมด้วย false

• คิว :=รายการใหม่

• กราฟ :=รายการย่อย n+1

• in_degree :=อาร์เรย์ขนาด n+1 และเติมด้วย 0

• สำหรับฉันแต่ละคนในความสัมพันธ์ทำ

  • แทรก i[1] ที่ส่วนท้ายของกราฟ[i[0]]

  • in_degree[i[1]] :=in_degree[i[1]] + 1

• เทอม :=1

• สำหรับผมอยู่ในช่วง 1 ถึง n+1 ทำ

  • ถ้า in_degree[i] เป็นศูนย์ แล้ว

    • ใส่ i ที่ท้ายคิว

    • เยี่ยมชม[i] :=จริง

• เทอม :=1

• รายวิชา :=รายวิชา - ขนาดคิว

• ในขณะที่คิวไม่ว่างและหลักสูตรไม่เป็นศูนย์ให้ทำ

  • current_size :=ขนาดของคิว

  • ในขณะที่ current_size ไม่ใช่ศูนย์ ให้ทำ

    • current_course :=คิว[0]

    • ลบองค์ประกอบแรกออกจากคิว

    • current_size :=current_size - 1

    • สำหรับแต่ละ i ในกราฟ[current_course] ทำ

      • in_degree[i] :=in_degree[i] - 1

      • ถ้าฉันไม่ได้รับการเยี่ยมชมและ in_degree[i] เป็นศูนย์

        • รายวิชา :=รายวิชา - 1

        • ใส่ i ที่ท้ายคิว

        • เยี่ยมชม[i]:=จริง

  • ภาคการศึกษา :=ภาคการศึกษา + 1

• กลับภาคการศึกษาถ้าหลักสูตรเป็น 0 มิฉะนั้น -1

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution(object):
   def minimumSemesters(self, n, relations):
      courses = n
      visited = [False for i in range(n+1)]
      queue = []
      graph = [[] for i in range(n+1)]
      in_degree = [0 for i in range(n+1)]
      for i in relations:
         graph[i[0]].append(i[1])
         in_degree[i[1]]+=1
      semeseter = 1
      for i in range(1,n+1):
         if not in_degree[i]:
            queue.append(i)
            visited[i] = True
         semester = 1
         courses -= len(queue)
         while queue and courses:
            current_size = len(queue)
            while current_size:
               current_course = queue[0]
               queue.pop(0)
               current_size-=1
               for i in graph[current_course]:
                  in_degree[i]-=1
                  if not visited[i] and not in_degree[i]:
                     courses-=1
                     queue.append(i)
                  visited[i]=True
            semester+=1
         return semester if not courses else -1

ob = Solution()
print(ob.minimumSemesters(3,[[1,3],[2,3]]))

อินพุต

3, [[1,3],[2,3]]

ผลลัพธ์

-1