पायथन में फॉरेस्ट को कनेक्ट करने का प्रोग्राम

मान लीजिए हमारे पास ग्राफ एडजेसेंसी लिस्ट के रूप में हैं। यह ग्राफ वास्तव में डिस्जॉइंट ट्री का एक सेट है। हमें फॉरेस्ट में कुछ एज जोड़नी हैं ताकि यह एक सिंगल ट्री बन जाए। हमें किन्हीं दो नोड्स के बीच सबसे लंबे पथ की न्यूनतम संभव दूरी वापस करनी है।

उदाहरण के लिए, दिए गए ग्राफ के लिए आउटपुट 4 होगा (एज 0->5 जोड़ने के बाद सबसे लंबा पथ 3-1-0-5-7 या 4-1-0-5-7, दूरी 4)।

एल्गोरिदम (ट्री डायमीटर + ग्रीडी मर्ज)

treeDepth(node) फ़ंक्शन: DFS से ट्री का डायमीटर और रेडियस (छत(डायमीटर/2)) की गणना करें
प्रत्येक ट्री के लिए treeDepth कॉल करें, opt में रेडियस संग्रहीत करें, sing में अधिकतम डायमीटर ट्रैक करें
यदि केवल एक ट्री है, तो sing वापस करें
सबसे बड़े रेडियस वाले ट्री का रेडियस 1 घटाएं, फिर सभी रेडियस में 1 जोड़ें (कनेक्टिंग एज के लिए)
दो सबसे बड़े रेडियस का योग और sing में से अधिकतम वापस करें

उदाहरण

import heapq, math
class Solution:
    def solve(self, graph):
        seen = set()
        dic = graph
        def treeDepth(node):
            self.ret = 0
            def dfs1(node, parent):
                seen.add(node)
                best2 = []
                for nxt in dic[node]:
                    if nxt != parent:
                        heapq.heappush(best2, dfs1(nxt, node)+1)
                if len(best2) > 2: heapq.heappop(best2)
                if not best2: return 0
                self.ret = max(self.ret, sum(best2))
                return max(best2)
            dfs1(node, None)
            return self.ret
        ret = 0; opt = []; sing = 0
        for node in range(len(graph)):
            if node in seen: continue
            res = treeDepth(node)
            sing = max(sing, res)
            opt.append(int(math.ceil(res/2)))
        if len(opt) <= 1: return sing
        mx = max(opt)
        for i in range(len(opt)):
            if opt[i] == mx:
                opt[i] -= 1
                break
        for i in range(len(opt)): opt[i] += 1
        high2 = heapq.nlargest(2, opt)
        return max(sum(high2), sing)

ob = Solution()
graph = [[1,2],[0,3,4],[0],[1],[1],[6,7],[5],[5]]
print(ob.solve(graph))

इनपुट

graph = [[1,2],[0,3,4],[0],[1],[1],[6,7],[5],[5]]