Python में निर्देशित ग्राफ में सबसे बड़ा रंग मान ज्ञात करें

एक निर्देशित ग्राफ दिया गया है जिसमें n रंगीन नोड्स और m एज हैं। प्रत्येक नोड का एक रंग (लोअरकेस अक्षर) है। एक वैध पथ नोड्स का अनुक्रम है जहां प्रत्येक नोड से अगले में निर्देशित एज है। पथ का रंग उस पथ में सबसे अधिक बार आने वाला नोड रंग है। सबसे बड़े रंग मान वाले वैध पथ को खोजें। यदि ग्राफ में साइकिल है तो -1 लौटाएं।

एल्गोरिदम: टोपोलॉजिकल सॉर्ट + डायनामिक प्रोग्रामिंग

1. इन-डिग्री (आने वाली एज) की गणना करें
2. क्यू में इन-डिग्री 0 वाले नोड्स डालें
3. dp[node][color]: उस नोड पर समाप्त होने वाले पथ में रंग की अधिकतम गिनती
4. टोपोलॉजिकल क्रम में प्रोसेस करें, पड़ोसियों को अपडेट करें
5. यदि सभी नोड्स विज़िट नहीं हुए → साइकिल मौजूद है → -1 लौटाएं
6. अन्यथा dp में अधिकतम मान लौटाएं

Python कार्यान्वयन

from collections import defaultdict, deque

def largest_color_value(colors, edges):
    """
    colors: स्ट्रिंग, colors[i] = नोड i का रंग ('a'-'z')
    edges: सूची of (u, v) निर्देशित एज
    return: अधिकतम रंग मान या -1 (यदि साइकिल)
    """
    n = len(colors)
    graph = defaultdict(list)
    indegree = defaultdict(int)
    
    # ग्राफ और इन-डिग्री बनाएं
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    
    # DP टेबल: n x 26 (प्रत्येक लोअरकेस अक्षर के लिए)
    dp = [[0] * 26 for _ in range(n)]
    color_vals = [ord(c) - ord('a') for c in colors]
    
    # क्यू इनिशियलाइज़ करें: इन-डिग्री 0 वाले नोड्स
    queue = deque()
    for u in range(n):
        if indegree[u] == 0:
            queue.append(u)
            dp[u][color_vals[u]] = 1
    
    visited = 0
    while queue:
        u = queue.popleft()
        visited += 1
        
        for v in graph[u]:
            # सभी 26 रंगों के लिए DP अपडेट
            for c in range(26):
                # यदि v का रंग c है तो 1 जोड़ें
                add = 1 if c == color_vals[v] else 0
                dp[v][c] = max(dp[v][c], dp[u][c] + add)
            
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)
                del indegree[v]
    
    # साइकिल जांच
    if visited < n:
        return -1
    
    # अधिकतम रंग मान
    return max(max(row) for row in dp)

# परीक्षण
colors = "aabada"
edges = [(0,1), (1,4), (1,2), (2,3), (3,5), (4,5)]
print(largest_color_value(colors, edges))  # आउटपुट: 4

व्याख्या

पथ 0 → 1 → 2 → 3 → 5 में रंग 'a' चार बार आता है (नोड्स 0, 1, 2, 5), जो अधिकतम है।

जटिलता

• समय: O(n × 26 + m × 26) = O(n + m) चूंकि 26 स्थिर है
• स्थान: O(n × 26) = O(n)

मुख्य बिंदु

• साइकिल डिटेक्शन: टोपोलॉजिकल सॉर्ट में सभी नोड्स प्रोसेस नहीं होते यदि साइकिल है
• DP स्टेट: नोड × रंग = उस रंग की अधिकतम गिनती
• रंगों को 0-25 इंडेक्स में मैप करें (ord(c) - ord('a'))
• deque O(1) पॉपलेफ्ट के लिए