โปรแกรมหาค่าสีที่ใหญ่ที่สุดในกราฟกำกับใน Python

สมมติว่าเรามีกราฟกำกับที่มีโหนดสี n โหนดและขอบต่างกัน m และโหนดมีหมายเลขตั้งแต่ 0 ถึง n-1 เรามีสตริง col ที่มีอักษรตัวพิมพ์เล็ก โดยที่ col[i] แทนสีของโหนด ith ในกราฟนี้ (ดัชนี 0 ดัชนี) นอกจากนี้เรายังมีรายการขอบที่ edge[j] =(u, v) แทน มีขอบระหว่าง u และ v

เส้นทางที่ถูกต้องในกราฟคือลำดับของโหนด xi สำหรับ i ทั้งหมดตั้งแต่ 1 ถึง k ซึ่งจะมีขอบตรงจาก xi ถึง xi+1 สีของเส้นทางคือสีโหนดที่พบบ่อยที่สุดของเส้นทางนั้น เราต้องหาค่าสีที่ใหญ่ที่สุดของเส้นทางที่ถูกต้องในกราฟนั้น หากมีวงจรในกราฟ ให้คืนค่า -1

ดังนั้น ถ้าอินพุตเป็นเหมือน col ="aabada" edge =[(0,1),(1,4),(1,2),(2,3),(3,5),(4,5) ],

จากนั้นผลลัพธ์จะเป็น 4 เนื่องจาก 0 -> 1 -> 2 -> 3 -> 5 มีเส้นทางที่ยาวที่สุดด้วยสี 'a'

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

• n:=ขนาดของ col

• graph:=กำหนดกราฟจากรายการขอบ

• indegree:=แผนที่ที่มีโหนดและค่าในระดับของพวกมัน

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

• dp:=สร้างอาร์เรย์ขนาด n x 26 และเติมด้วย 0

• colorvalues:=สร้างรายการโดยเรียงลำดับ c ในตัวอักษรสำหรับ c ทั้งหมดใน col

• สำหรับคุณในช่วง 0 ถึง n - 1 ทำ

  • ถ้าคุณไม่ได้อยู่ใน indegree แล้ว

    • ใส่ u ท้ายคิว

    • dp[u, ค่าสี[u]]:=1

• เข้าชมแล้ว:=0

• ขณะที่คิวไม่ว่างให้ทำ

  • u:=องค์ประกอบด้านหน้าของคิวและลบออกหลังจาก

  • เยี่ยมชม :=เยี่ยมชม + 1

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

    • สำหรับ c ในช่วง 0 ถึง 25 ทำ

      • dp[v, c] =สูงสุดของ dp[v, c] และ (dp[u, c] + (1 ถ้า c เป็นค่าเดียวกับค่าสี[v] มิฉะนั้น 0)

    • indegree[v] :=indegree[v] - 1

    • ถ้า indegree[v] เท่ากับ 0 แล้ว

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

      • del indegree[v]

• ถ้ามา

  • กลับ -1

• คืนค่าองค์ประกอบสูงสุดใน dp

ตัวอย่าง

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

from collections import defaultdict
def solve(col, edges):
   n=len(col)
   graph=defaultdict(list)
   indegree=defaultdict(int)

   for u,v in edges:
      graph[u].append(v)
      indegree[v]+=1

   queue=[]
   dp=[[0]*26 for _ in range(n)]
   colorvalues=[ord(c)-ord("a") for c in col]
   for u in range(n):
      if u not in indegree:
         queue.append(u)
         dp[u][colorvalues[u]]=1

   visited=0
   while queue:
      u=queue.pop()
      visited+=1

      for v in graph[u]:
         for c in range(26):
            dp[v][c]=max(dp[v][c],dp[u][c] + (c==colorvalues[v]))
         indegree[v]-=1
         if indegree[v]==0:
            queue.append(v)
            del indegree[v]
   if visited<n:
      return -1
   return max(max(x) for x in dp)

col = "aabada"
edges = [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]
print(solve(col, edges))

อินพุต

"aabada", [(0,1),(1,4),(1,2),(2,3),(3,5),(4,5)]

ผลลัพธ์

4