สมมติว่าเรามีกราฟกำกับที่มีโหนดสี 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