Pagini recente » Cod sursa (job #354225) | Cod sursa (job #2111780) | Cod sursa (job #2457347) | Cod sursa (job #197260) | Cod sursa (job #3258973)
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()