পাইথনে ফরেস্ট সংযোগ করুন

একাধিক বিচ্ছিন্ন গাছ (ফরেস্ট) দেওয়া আছে। এই গাছগুলোকে প্রান্ত যোগ করে একটি একক গাছে পরিণত করতে হবে যেন সবচেয়ে দীর্ঘ পথের দৈর্ঘ্য ন্যূনতম হয়।

উদাহরণ গ্রাফ দিয়ে আউটপুট ৪।

সমাধানের ধাপসমূহ

প্রতিটি গাছের গভীরতা (depth) এবং ব্যাসার্ধ (radius) বের করুন
সবচেয়ে বড় ব্যাসার্ধ वाली গাছের ব্যাসার্ধ ১ কমানো
সব গাছের ব্যাসার্ধ ১ বাড়িয়ে দুটি সর্বোচ্চ যোগ করুন
সিংগেল গাছের সর্বোচ্চ দৈর্ঘ্য এবং যুগল যোগফলের মধ্যে সর্বোচ্চ ফেরত দিন

উদাহরণ কোড

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