Pagini recente » Cod sursa (job #1839885) | Cautari ortogonale | Cod sursa (job #1801447) | Cod sursa (job #1762975) | Cod sursa (job #3258975)
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()