Cod sursa(job #3258975)

Utilizator MateitzaMatei Dinu Mateitza Data 24 noiembrie 2024 16:23:35
Problema Diametrul unui arbore Scor 70
Compilator py Status done
Runda Arhiva educationala Marime 1.61 kb
class Solution:
    def solveProblem(self):
        def read_file():
            # Dictionary to store edges
            graph = {}
            with open('darb.in', 'r') as f:
                n = int(f.readline())
                # Read and process each edge
                for _ in range(n - 1):
                    u, v = map(int, f.readline().split())
                    # Initialize lists if needed
                    if u not in graph: graph[u] = []
                    if v not in graph: graph[v] = []
                    # Add edges
                    graph[u].append(v)
                    graph[v].append(u)
            return graph
        
        def find_farthest(start, parent=-1, graph=None):
            max_dist = 0
            max_node = start
            
            for neighbor in graph[start]:
                if neighbor != parent:
                    dist, node = find_farthest(neighbor, start, graph)
                    if dist + 1 > max_dist:
                        max_dist = dist + 1
                        max_node = node
            
            return max_dist, max_node

        # Build graph
        tree = read_file()

        # Find the farthest node from an arbitrary start
        start = next(iter(tree))
        _, far_node = find_farthest(start, -1, tree)
        
        # Find the actual diameter starting from the farthest node
        diameter, _ = find_farthest(far_node, -1, tree)
        
        # Write result
        with open('darb.out', 'w') as f:
            f.write(str(diameter + 1))

if __name__ == "__main__":
    Solution().solveProblem()