https://www.acmicpc.net/problem/1967
initial
This question has kind of a mathematical formula (which i didnt know) where the node furthest and most costly from root will be the furthest and most costly for a node. So if we do dfs search from root and get the costliest node’s value, then do another dfs search from that costliest node, the output distance list will contain distances from that node to all other nodes. We get the max value from that list and print it.
solution
rmb to mark distance[your_starting_point] as 0.
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
graph = defaultdict(list)
for _ in range(n-1):
a, b, c = map(int, input().split())
graph[a].append((b, c))
graph[b].append((a, c))
def dfs(index, distance):
for hola in graph[index]:
node, cost = hola
if distance[node] == -1:
distance[node] = distance[index] + cost
dfs(node, distance)
distance = [-1 for _ in range(n + 1)]
distance[1]=0
dfs(1, distance)
index = distance.index(max(distance))
distance = [-1 for _ in range(n + 1)]
distance[index]=0
dfs(index, distance)
index = distance.index(max(distance))
print(distance[index])complexity
is it v+e cuz even tho we are doing dfs twice it is constant so 2(v+e) is rounded to v+e?
YES!
Time Complexity:
The graph is represented using an adjacency list, and the DFS function is used to traverse the graph. The time complexity of the DFS is O(V + E), where V is the number of vertices and E is the number of edges.
The loop that initializes the distance array has a time complexity of O(n), where n is the number of vertices.
The second part of the code that calculates the distances twice also involves DFS, so its time complexity is O(V + E).
The overall time complexity is O(V + E).
Space Complexity:
The space complexity is determined by the space required for the adjacency list (graph), the distance array, and the recursive call stack during DFS.
The space required for the adjacency list is O(V + E), where V is the number of vertices and E is the number of edges.
The space complexity of the distance array is O(V).
The space complexity of the recursive call stack in the DFS function is O(V) in the worst case.
The overall space complexity is O(V + E).
In summary, the provided code has a time complexity of O(V + E) and a space complexity of O(V + E).
