पायथन में निर्देशित ग्राफ में सबसे बड़ा रंग मान खोजने का कार्यक्रम

मान लीजिए कि हमारे पास n रंगीन नोड्स और m विभिन्न किनारों के साथ एक निर्देशित ग्राफ है। और नोड्स 0 से n-1 तक गिने जाते हैं। हमारे पास लोअरकेस अक्षरों वाला एक स्ट्रिंग कॉल है, जहां col[i] इस ग्राफ (0-अनुक्रमित) में ith नोड के रंग का प्रतिनिधित्व करता है। हमारे पास एक किनारे की सूची भी है जहां किनारों [जे] =(यू, वी) का प्रतिनिधित्व करता है, वहां यू और वी के बीच एक किनारा है।

ग्राफ़ में एक मान्य पथ 1 से k तक सभी i के लिए नोड्स xi का अनुक्रम है, जैसे कि xi से xi+1 तक एक निर्देशित किनारा है। पथ का रंग उस पथ का सबसे लगातार नोड रंग है। हमें उस ग्राफ में किसी भी मान्य पथ का सबसे बड़ा रंग मान ज्ञात करना है। अगर ग्राफ में कोई साइकिल है तो -1 लौटें।

तो, अगर इनपुट col ="aabada" किनारों =[(0,1),(1,4),(1,2),(2,3),(3,5),(4,5) की तरह है ],

तो आउटपुट 4 होगा 0 -> 1 -> 2 -> 3 -> 5 रंग 'ए' के साथ सबसे लंबा पथ है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

n:=कर्नल का आकार
ग्राफ़:=किनारे की सूची से दिया गया ग्राफ़
डिग्री:=नक्शा जिसमें नोड्स और उनके इन-डिग्री मान शामिल हैं
कतार:=एक नई सूची
dp:=n x 26 आकार की एक सरणी बनाएं, और 0 से भरें
colorvalues:=col में सभी c के लिए वर्णमाला में c के क्रम के साथ एक सूची बनाएं
आपके लिए 0 से n -1 की सीमा में, करें
- अगर आप डिग्री में नहीं हैं, तो
  - आपको कतार के अंत में सम्मिलित करें
  - dp[u, colorvalues[u]]:=1
विज़िट किया गया:=0
जबकि कतार खाली नहीं है, करें
- u:=कतार का अगला तत्व और बाद में इसे हटा दें
- विज़िट किया गया :=विज़िट किया गया + 1
- ग्राफ़ में प्रत्येक v के लिए[u], करें
  - सी के लिए 0 से 25 की सीमा में, करें
    - dp[v, c] =अधिकतम dp[v, c] और (dp[u, c] + (1 यदि c समान रंगमान [v] है, अन्यथा 0)
  - डिग्री [वी] :=डिग्री [वी] - 1
  - अगर डिग्री [v] 0 के समान है, तो
    - कतार के अंत में v डालें
    - डेल इंडिग्री[v]
अगर विज़िट किया गया
- वापसी -1
डीपी में अधिकतम तत्व लौटाएं

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें

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)]