Cod sursa(job #3258973)

Utilizator MateitzaMatei Dinu Mateitza Data 24 noiembrie 2024 16:18:05
Problema Diametrul unui arbore Scor 70
Compilator py Status done
Runda Arhiva educationala Marime 1.87 kb
class Solution:
    def solveProblem(self):
        hashmap_node_neighbors = {}
        
        def read_file(file_name: str):
            with open(file_name, 'r') as f:
                n = int(f.readline())
                # Read edges directly without storing all lines
                for _ in range(1, n):
                    node, neighbor = map(int, f.readline().split())
                    
                    if node not in hashmap_node_neighbors:
                        hashmap_node_neighbors[node] = []
                    if neighbor not in hashmap_node_neighbors:
                        hashmap_node_neighbors[neighbor] = []
                    
                    hashmap_node_neighbors[node].append(neighbor)
                    hashmap_node_neighbors[neighbor].append(node)
        
        def dfs(node: int, parent: int):
            max_depth = 0
            max_node = node
            
            for next_node in hashmap_node_neighbors[node]:
                if next_node != parent:  # Only visit if not parent
                    depth, far_node = dfs(next_node, node)
                    if depth + 1 > max_depth:
                        max_depth = depth + 1
                        max_node = far_node
            
            return max_depth, max_node

        # Main execution
        read_file('darb.in')
        
        # Start from node 1 (or first node in graph)
        start_node = min(hashmap_node_neighbors.keys())
        
        # First DFS to find farthest node
        _, farthest_node = dfs(start_node, -1)
        
        # Second DFS from farthest node to get diameter
        diameter, _ = dfs(farthest_node, -1)
        
        # Write result
        with open('darb.out', 'w') as f:
            f.write(str(diameter + 1))  # +1 because we need number of nodes in path

sol = Solution()
sol.solveProblem()